{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "52fc3cf9",
   "metadata": {},
   "source": [
    "## 平面点集中查找举例最近的两个点\n",
    "\n",
    "1. 绘制对应的散点图\n",
    "2. 查找算法的基本步骤\n",
    "3. 数据结构\n",
    "    1. Point\n",
    "    2. class atributes: x, y, is_left\n",
    "    3. __str__, __distance__\n",
    "4. 设计思想\n",
    "    1. 将点集分割为两个点数相近的子集 -> seperate_points_by_median\n",
    "    2. 分别在两个子集中递归查找两点之间的最短距离 -> find_closest_pair\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "4a148de0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAjEAAAGdCAYAAADjWSL8AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8pXeV/AAAACXBIWXMAAA9hAAAPYQGoP6dpAAA36ElEQVR4nO3df3RU9Z3/8dckIQllkykJJJMxkbJUrTEIK4uKmwMqkLAVAvbsAXW1uuW4Fkm64VcRdzk03541Yq3WHwc827VwSg5k9w8CYXVTw0qiOZiqiUhTPNCyOQqS2fQIOyE0CSFzv3+wM2VIQpjJzczcO8/HOXMOc+czd+58mMl9z/vzue+PwzAMQwAAABaTEO0DAAAACAdBDAAAsCSCGAAAYEkEMQAAwJIIYgAAgCURxAAAAEsiiAEAAJZEEAMAACwpKdoHEA6fz6czZ84oLS1NDocj2ocDAACug2EYOn/+vNxutxISRp9HsWQQc+bMGeXl5UX7MAAAQBhOnTql3NzcUe/HkkFMWlqapMudkJ6eHuWjAQAA16Orq0t5eXmB8/hoWTKI8Q8hpaenE8QAAGAxZk0FYWIvAACwJIIYAABgSQQxAADAkghiAACAJRHEAAAASwopiNm+fbtuv/32wFVBc+bM0X/+538GHjcMQz/60Y/kdrs1fvx43Xvvvfrtb38btI++vj6VlZVp0qRJmjBhgkpKSnT69Glz3g0AAIgbIQUxubm5ev755/Xxxx/r448/1v3336+lS5cGApUXXnhBL730kl5//XV99NFHcrlcWrhwoc6fPx/YR3l5uWpqalRdXa2mpiZ1d3dr8eLFGhgYMPedAQAAW3MYhmGMZgcZGRn6yU9+ou9973tyu90qLy/Xxo0bJV3OumRnZ2vr1q166qmn5PV6NXnyZO3atUsrVqyQ9Kfqu2+//baKi4uv6zW7urrkdDrl9XqpEwMAgEWYff4Oe07MwMCAqqurdeHCBc2ZM0ft7e3yeDwqKioKtElJSdG8efN0+PBhSVJLS4v6+/uD2rjdbhUUFATaDKWvr09dXV1BN8DuBnyGPjj5lfYf+VIfnPxKA75R/d4AANsJuWLvb37zG82ZM0e9vb36sz/7M9XU1Cg/Pz8QhGRnZwe1z87O1ueffy5J8ng8Sk5O1sSJEwe18Xg8w75mZWWlKioqQj1UwLLq2jpUceCYOry9gW05zlRtWZKvRQU5UTwyAIgdIWdibrnlFh05ckTNzc1atWqVHn/8cR07dizw+NWlhA3DGLG88EhtNm3aJK/XG7idOnUq1MMGLKOurUOrqlqDAhhJ8nh7taqqVXVtHVE6MgCILSEHMcnJyfrmN7+pv/zLv1RlZaVmzJihV155RS6XS5IGZVQ6OzsD2RmXy6WLFy/q3Llzw7YZSkpKSuCKKKusl8RQAMIx4DNUceCYhvq0+LdVHDjG5wkAZEKdGMMw1NfXp6lTp8rlcqm+vj7w2MWLF9XY2Kh77rlHkjRr1iyNGzcuqE1HR4fa2toCbeygrq1DhVvf1cM/b9Y/VB/Rwz9vVuHWd/kFjRF92H52UAbmSoakDm+vPmw/G7mDAoAYFdKcmGeffVZ//dd/rby8PJ0/f17V1dVqaGhQXV2dHA6HysvL9dxzz+mmm27STTfdpOeee05f+9rX9Mgjj0iSnE6nVq5cqXXr1ikzM1MZGRlav369pk+frgULFozJG4w0/1DA1b+T/UMB2x+9gzkNGFbn+eEDmHDaAYCdhRTE/M///I8ee+wxdXR0yOl06vbbb1ddXZ0WLlwoSfrhD3+onp4ePf300zp37pzuuusuvfPOO0pLSwvs4+WXX1ZSUpKWL1+unp4ezZ8/Xzt37lRiYqK57ywKRhoKcOjyUMDCfJcSE8xZhhz2kpWWamo7ALCzUdeJiYZYrRPzwcmv9PDPm0dst+fJuzVnWmYEjghWM+AzVLj1XXm8vUMGww5JLmeqmjbeTyAM2NCAz9CH7WfVeb5XWWmpunNqhq2+62afv0O+xBrDYygAo5WY4NCWJflaVdUqhxQUyPj/jG1Zkm+rP2oALqO0QuhYANJEDAXADIsKcrT90TvkcgZ/TlzOVOZUATZFaYXwkIkx0Z1TM5TjTB1xKODOqRmRPjRYzKKCHC3Md9k6rQyEw47DLcynDB9BjIkYCoCZEhMczJ0CrmDX4ZZQSivwNyEYw0kmYygAAMxn5+GWaM6ntHphVjIxY4ChAAAwj92HW6I1n9IOmS0yMWPEPxSwdOYNmjMt05JfLMQeq/9qAsJh90rW/vmUw50lHLocXJg5n9IumS0yMYBF2OFXExAOu5eviPR8SjtltsjEABZgl19NQDjioXxFJOdT2imzRSYGiHF2+tUEhCNeyldEaj6lnTJbZGKAGGenX01AOPzDLZIGzRuxW/mKSMyntFNmiyAGiHF2+tUEhIvyFeaJxkTiscJwEhDj7PSrCRgNyleYw06FWcnEADHOTr+agNGifIU57JLZIhMDxDg7/WoCEDvskNlyGIZhuWpZXV1dcjqd8nq9Sk9Pj/bhABFBnRgAVmf2+ZtMDGARdvjVBABmIogBLISVrQHgT5jYCwAALIkgBgAAWBJBDAAAsCSCGAAAYEkEMQAAwJIIYgAAgCURxAAAAEsiiAEAAJZEEAMAACyJir0AgLgz4DNYwsMGCGIAAHGFxVTtg+EkAEDcqGvr0Kqq1qAARpI83l6tqmpVXVtHlI4M4SCIAQDEhQGfoYoDx2QM8Zh/W8WBYxrwDdUCsYggBgAQFz5sPzsoA3MlQ1KHt1cftp+N3EFhVAhiAABxofP88AFMOO0QfUzsjTHMmAeAsZGVlmpqO0RfSJmYyspKzZ49W2lpacrKytKyZct0/PjxoDbd3d0qLS1Vbm6uxo8fr1tvvVXbt28PatPX16eysjJNmjRJEyZMUElJiU6fPj36d2NxdW0dKtz6rh7+ebP+ofqIHv55swq3vstEMwAwwZ1TM5TjTNVwPwsdunyV0p1TMyJ5WBiFkIKYxsZGrV69Ws3Nzaqvr9elS5dUVFSkCxcuBNqsWbNGdXV1qqqq0meffaY1a9aorKxM+/fvD7QpLy9XTU2Nqqur1dTUpO7ubi1evFgDAwPmvTOLYcY8AIytxASHtizJl6RBgYz//pYl+WS/LcRhGEbY07D/8Ic/KCsrS42NjZo7d64kqaCgQCtWrNDmzZsD7WbNmqVvf/vb+vGPfyyv16vJkydr165dWrFihSTpzJkzysvL09tvv63i4uIRX7erq0tOp1Ner1fp6enhHn7MGPAZKtz67rATzhySXM5UNW28ny8XAIwSdWKix+zz96jmxHi9XklSRsafUm+FhYWqra3V9773PbndbjU0NOjEiRN65ZVXJEktLS3q7+9XUVFR4Dlut1sFBQU6fPjwkEFMX1+f+vr6Ave7urpGc9gxJ5QZ83OmZUbuwADAhhYV5Ghhvov5hzYQdhBjGIbWrl2rwsJCFRQUBLa/+uqrevLJJ5Wbm6ukpCQlJCToX//1X1VYWChJ8ng8Sk5O1sSJE4P2l52dLY/HM+RrVVZWqqKiItxDjXnMmAeAyEpMcPCj0AbCvsS6tLRUR48e1Z49e4K2v/rqq2publZtba1aWlr005/+VE8//bQOHjx4zf0ZhiGHY+goeNOmTfJ6vYHbqVOnwj3smMSMeQAAQhdWJqasrEy1tbV67733lJubG9je09OjZ599VjU1NXrggQckSbfffruOHDmiF198UQsWLJDL5dLFixd17ty5oGxMZ2en7rnnniFfLyUlRSkpKeEcqiX4Z8x7vL1DVpL0z4lhxjwQHyi1AFyfkDIxhmGotLRUe/fu1bvvvqupU6cGPd7f36/+/n4lJATvNjExUT6fT9LlSb7jxo1TfX194PGOjg61tbUNG8TYHTPmAfhRagG4fiEFMatXr1ZVVZV2796ttLQ0eTweeTwe9fT0SJLS09M1b948bdiwQQ0NDWpvb9fOnTv1y1/+Ug8++KAkyel0auXKlVq3bp3+67/+S5988okeffRRTZ8+XQsWLDD/HVrEooIcbX/0DrmcwUNGLmeqtj96BzPmgThAqQUgNCFdYj3cnJUdO3boiSeekHR54u6mTZv0zjvv6OzZs5oyZYr+/u//XmvWrAk8v7e3Vxs2bNDu3bvV09Oj+fPna9u2bcrLy7uu47DbJdZXIo0MxCdKLSAemH3+HlWdmGixcxADID59cPIrPfzz5hHb7Xnybq6qgWXFVJ0YAIA5KLUQfWTCrYcgBgBiAKUWoosqvtYUdp0YAIB5WJwwephQbV0EMQAQAyi1EB0DPkMVB44NWaPLv63iwDEN+Cw3fTQuEMQAQIyg1ELkhbJ2HWIPc2IAIIawOGFkMaHa2ghiACDGsDhh5DCh2toYTgIAxC0mVFsbQQwAIG4xodraCGIwogGfoQ9OfqX9R77UBye/YpY+AFthQrV1MScG10QBKADxgAnV1sTaSRiWvwDU1R8Q/1eaXygAYD9jufwCaychIkYqAOXQ5QJQC/Nd/FIBAJuwWvadOTEYEgWgACC+WHH5BYIYDIkCUAAQP6y6/AJBDIZEASgAiB9Wzb4TxGBIFIACgPhh1ew7QQyGRAEoAIgfVs2+E8RgWBSAAoD4YNXsO5dY45ooAAUA9ufPvq+qapVDCprgG8vZd4rdAQAASWNfJ4ZidwAAYExYLftOEAMAsL2xLKUfC69npsQEh+ZMy4z2YVwXghgAgK1FupS+1Ur3WxlXJwEAbCvSpfStWLrfyghiAAC2FOlS+lYt3W9lBDEAAFuKdCl9q5butzKCGACALUW6lL5VS/dbGUEMAMCWIl1K36ql+62MIAYAYEuRLqVv1dL9VkYQAwCwpUgvZMvCuZFHEAPEqAGfoQ9OfqX9R77UBye/4oqGMUI/21ukF7Jl4dzIYu0kIAZRLCsy6Of4QcXe2GD2+ZsgBogx/mJZV38x/X/++DVnDvoZiDyzz98MJwExhGJZkUE/xx6G9RCOkIKYyspKzZ49W2lpacrKytKyZct0/PjxQe0+++wzlZSUyOl0Ki0tTXfffbe++OKLwON9fX0qKyvTpEmTNGHCBJWUlOj06dOjfzeAxVEsKzLo59hS19ahwq3v6uGfN+sfqo/o4Z83q3Dru5Tox4hCCmIaGxu1evVqNTc3q76+XpcuXVJRUZEuXLgQaHPy5EkVFhbqW9/6lhoaGvTpp59q8+bNSk390ySn8vJy1dTUqLq6Wk1NTeru7tbixYs1MDBg3jsDLIhiWZFBP8cO1hrCaIS0inVdXV3Q/R07digrK0stLS2aO3euJOkf//Ef9e1vf1svvPBCoN2f//mfB/7t9Xr15ptvateuXVqwYIEkqaqqSnl5eTp48KCKi4vDfjOA1VEsKzLo59gw0rCeQ5eH9Rbmu5gUiyGNak6M1+uVJGVkXC7c4/P59NZbb+nmm29WcXGxsrKydNddd2nfvn2B57S0tKi/v19FRUWBbW63WwUFBTp8+PCQr9PX16eurq6gG2BHFMuKDPo5NjCsh9EKO4gxDENr165VYWGhCgoKJEmdnZ3q7u7W888/r0WLFumdd97Rgw8+qO985ztqbGyUJHk8HiUnJ2vixIlB+8vOzpbH4xnytSorK+V0OgO3vLy8cA8biGkUy4oM+jk2MKyH0Qo7iCktLdXRo0e1Z8+ewDafzydJWrp0qdasWaOZM2fqmWee0eLFi/XGG29cc3+GYcjhGPoPxqZNm+T1egO3U6dOhXvYQMyjWFZk0M/Rx7AeRiukOTF+ZWVlqq2t1Xvvvafc3NzA9kmTJikpKUn5+flB7W+99VY1NTVJklwuly5evKhz584FZWM6Ozt1zz33DPl6KSkpSklJCedQAUtaVJCjhfkuimWNMfo5uvzDeh5v75DzYhy6HFQyrIfhhJSJMQxDpaWl2rt3r959911NnTo16PHk5GTNnj170GXXJ06c0JQpUyRJs2bN0rhx41RfXx94vKOjQ21tbcMGMUA8SkxwaM60TC2deYPmTMvkxDpG6OfoYVgPoxVSJmb16tXavXu39u/fr7S0tMAcFqfTqfHjx0uSNmzYoBUrVmju3Lm67777VFdXpwMHDqihoSHQduXKlVq3bp0yMzOVkZGh9evXa/r06YGrlYDrQVlvwPr8w3pXL//gYvkHXIeQlh0Ybs7Kjh079MQTTwTu/+IXv1BlZaVOnz6tW265RRUVFVq6dGng8d7eXm3YsEG7d+9WT0+P5s+fr23btl33hF2WHQBr3gD2wo+S+MDaSSKIiXeseQMA1sTaSYhrrHkDAPAjiIGlUBwLAOBHEANLoTgWAMCPIAaWQnEsAIAfQQwshTVvAAB+BDGwFIpjAQD8CGJgOax5AwCQwlw7CYg21rwBABDEXIGKkdbiX/MGABCfCGL+D2XsAQCwFubE6E9l7K8uoubx9mpVVavq2jqidGQAAGA4cR/EUMYeAABrivsghjL2AABYU9wHMZSxBwDAmuI+iKGMPQAA1hT3QQxl7AEAsKa4D2IoYw8AgDXFfRAjUcYeAAArotjd/6GMPQAA1kIQcwXK2AMAYB0MJwEAAEsiiAEAAJZEEAMAACyJIAYAAFgSQQwAALAkghgAAGBJBDEAAMCSCGIAAIAlEcQAAABLIogBAACWRBADAAAsiSAGAABYEkEMAACwJIIYAABgSSEFMZWVlZo9e7bS0tKUlZWlZcuW6fjx48O2f+qpp+RwOPSzn/0saHtfX5/Kyso0adIkTZgwQSUlJTp9+nRYbwAAAMSnkIKYxsZGrV69Ws3Nzaqvr9elS5dUVFSkCxcuDGq7b98+/frXv5bb7R70WHl5uWpqalRdXa2mpiZ1d3dr8eLFGhgYCP+dAACAuJIUSuO6urqg+zt27FBWVpZaWlo0d+7cwPYvv/xSpaWl+tWvfqUHHngg6Dler1dvvvmmdu3apQULFkiSqqqqlJeXp4MHD6q4uDjc9wIAAOLIqObEeL1eSVJGRkZgm8/n02OPPaYNGzbotttuG/SclpYW9ff3q6ioKLDN7XaroKBAhw8fHvJ1+vr61NXVFXQDAADxLewgxjAMrV27VoWFhSooKAhs37p1q5KSkvSDH/xgyOd5PB4lJydr4sSJQduzs7Pl8XiGfE5lZaWcTmfglpeXF+5hAwAAmwg7iCktLdXRo0e1Z8+ewLaWlha98sor2rlzpxwOR0j7Mwxj2Ods2rRJXq83cDt16lS4hw0AAGwirCCmrKxMtbW1OnTokHJzcwPb33//fXV2durGG29UUlKSkpKS9Pnnn2vdunX6xje+IUlyuVy6ePGizp07F7TPzs5OZWdnD/l6KSkpSk9PD7oh2IDP0Acnv9L+I1/qg5NfacBnRPuQAAAYUyFN7DUMQ2VlZaqpqVFDQ4OmTp0a9Phjjz0WmKzrV1xcrMcee0x/93d/J0maNWuWxo0bp/r6ei1fvlyS1NHRoba2Nr3wwgujeS9xq66tQxUHjqnD2xvYluNM1ZYl+VpUkBPFIwMAYOyEFMSsXr1au3fv1v79+5WWlhaYw+J0OjV+/HhlZmYqMzMz6Dnjxo2Ty+XSLbfcEmi7cuVKrVu3TpmZmcrIyND69es1ffr0QQEQRlbX1qFVVa26Ou/i8fZqVVWrtj96B4EMAMCWQhpO2r59u7xer+69917l5OQEbv/2b/8W0ou+/PLLWrZsmZYvX66/+qu/0te+9jUdOHBAiYmJIe0n3g34DFUcODYogJEU2FZx4BhDSwAAW3IYhmG5M1xXV5ecTqe8Xm9cz4/54ORXevjnzSO22/Pk3ZozLXPEdgAAjCWzz9+snWRhned7R24UQjsAAKyEIMbCstJSTW0HAICVEMRY2J1TM5TjTNVwFXkcunyV0p1TM4ZpAQCAdRHEWFhigkNbluRL0qBAxn9/y5J8JSaEVngQAAArIIixuEUFOdr+6B1yOYOHjFzOVC6vBgDYWkh1YhCbFhXkaGG+Sx+2n1Xn+V5lpV0eQiIDAwCwM4IYm0hMcHAZtYUM+AyCTiAMfHdwJYIYIMJYJgIID98dXI05MUAE+ZeJuPKPsPSnZSLq2jqidGRAbOO7g6EQxAARwjIRQHj47mA4BDFAhHzYfnbQr8grGZI6vL36sP1s5A4KsAC+OxgOQQwQISwTAYSH7w6GQxADRAjLRADh4buD4RDEABHCMhFAePjuYDgEMUCEsEwEEB6+OxgOQQwQQSwTAYSH7w6G4jAMw3LXpHV1dcnpdMrr9So9PT3ahwOEjKqjQHj47lib2edvKvYCUcAyEUB4+O7gSgwnAQAASyKIAQAAlkQQAwAALIkgBgAAWBJBDAAAsCSCGAAAYElcYm1j1FMAANgZQYxN1bV1qOLAsaDl63OcqdqyJJ/KlgAAW2A4yYbq2jq0qqo1KICRJI+3V6uqWlXX1hGlIwMAwDwEMTYz4DNUceCYhlpLwr+t4sAxDfgst9qEZQ34DH1w8ivtP/KlPjj5FX0PACZhOMlmPmw/OygDcyVDUoe3Vx+2n6V0dwQwrAcAY4dMjM10nh8+gAmnHcLHsB4AjC2CGJvJSksduVEI7RAehvUAYOwxnGQzd07NUI4zVR5v75AnUIckl/Py5dZ2FCuXlTOsF5ti5fMBwBwEMTaTmODQliX5WlXVKocUFMj4/1RvWZJvyz/csTT/hGG92BNLnw8A5mA4yYYWFeRo+6N3yOUMHjJyOVO1/dE7bPkHO9bmnzCsF1ti7fMBwBwhBTGVlZWaPXu20tLSlJWVpWXLlun48eOBx/v7+7Vx40ZNnz5dEyZMkNvt1ne/+12dOXMmaD99fX0qKyvTpEmTNGHCBJWUlOj06dPmvCNIuhzING28X3uevFuvPDRTe568W00b77dlABOL80/8w3rD5bscupwFsOuwXiyJxc8HAHOEFMQ0NjZq9erVam5uVn19vS5duqSioiJduHBBkvTHP/5Rra2t2rx5s1pbW7V3716dOHFCJSUlQfspLy9XTU2Nqqur1dTUpO7ubi1evFgDAwPmvTMoMcGhOdMytXTmDZozLdOWQ0hSaPNPIsU/rCdpUCBj92G9WBOLnw8A5ghpTkxdXV3Q/R07digrK0stLS2aO3eunE6n6uvrg9q89tpruvPOO/XFF1/oxhtvlNfr1Ztvvqldu3ZpwYIFkqSqqirl5eXp4MGDKi4uHuVbQryJ1fkn/mG9q+dhuJiHEVGx+vkAMHqjmtjr9XolSRkZw6fEvV6vHA6Hvv71r0uSWlpa1N/fr6KiokAbt9utgoICHT58mCAGIYvl+SeLCnK0MN/FFTFRFMufDwCjE3YQYxiG1q5dq8LCQhUUFAzZpre3V88884weeeQRpaenS5I8Ho+Sk5M1ceLEoLbZ2dnyeDxD7qevr099fX2B+11dXeEeNmwo1i8r9w/rITpi/fMBXIkyAKEJO4gpLS3V0aNH1dTUNOTj/f39euihh+Tz+bRt27YR92cYhhyOof+jKisrVVFREe6hwubi+bJyjIzPB6yCMgChC+sS67KyMtXW1urQoUPKzc0d9Hh/f7+WL1+u9vZ21dfXB7IwkuRyuXTx4kWdO3cu6DmdnZ3Kzs4e8vU2bdokr9cbuJ06dSqcw4aNxeNl5bh+fD4Q6ygDEB6HYRjXfV2hYRgqKytTTU2NGhoadNNNNw1q4w9gfve73+nQoUOaPHly0ONer1eTJ09WVVWVli9fLknq6OhQbm6u3n777euaE9PV1SWn0ymv1xsUIAGkYnEtfD4QiwZ8hgq3vjvsVXT+Ic+mjfdb/vNq9vk7pOGk1atXa/fu3dq/f7/S0tICc1icTqfGjx+vS5cu6W/+5m/U2tqq//iP/9DAwECgTUZGhpKTk+V0OrVy5UqtW7dOmZmZysjI0Pr16zV9+vTA1UpAuJh/gmvh84FYxDIl4QspiNm+fbsk6d577w3avmPHDj3xxBM6ffq0amtrJUkzZ84ManPo0KHA815++WUlJSVp+fLl6unp0fz587Vz504lJiaG9y4AABgDkcjeUQYgfCEFMSONPH3jG98YsY0kpaam6rXXXtNrr70WyssDABAxkZpoSxmA8LF2EgAAV4nkRFuWKQkfQQwAAFeI9Hpb/jIAw+3NEGUAhkMQAwDAFVhvyzoIYgAAuEKkJ9r6Mz/DcYiV1odDEAMAwBUiPdGWzE/4CGIAALiCf6LttZg50ZZLrMNHEAMAwBUSExwqmXHtS6hLZuSYNtGWS6zDRxADAMAVBnyGaj+99iXUtZ92mDZHhUusw0cQAwDAFUaaoyKZO0fFf4m1pEGBDCutXxtBDAAAV4jGHBVWWg9PSMsOAABgd9Gao7KoIEcL812stB4CghgAAK7gn6Pi8fYOWUXXocsZkrGYo8JK66FhOAkAgCswR8U6CGIAALgKc1SsgeEkAACGwByV2EcQAwDAMJijEtsYTgIAAJZEEAMAACyJIAYAAFgSQQwAALAkghgAAGBJBDEAAMCSCGIAAIAlEcQAAABLIogBAACWRBADAAAsiSAGAABYEmsnAXFgwGewiB0A2yGIAWyurq1DFQeOqcPbG9iW40zVliX5WlSQE8UjA4DRYTgJsLG6tg6tqmoNCmAkyePt1aqqVtW1dUTpyACYacBn6IOTX2n/kS/1wcmvNOAzYmJfY41MDGBTAz5DFQeOaag/P4Ykh6SKA8e0MN/F0BJgYWZmW62WuSUTA9jUh+1nB2VgrmRI6vD26sP2s5E7KACmMjPbasXMLUEMbM1KaVGzdZ4fPoAJpx2A2DJStlW6nG29nr97Zu4rkhhOgm1ZLS1qtqy0VFPbAYgtoWRb50zLjNi+IolMDGzJimlRs905NUM5zlQNN9vFoctB3Z1TMyJ5WABMYma21aqZ25CCmMrKSs2ePVtpaWnKysrSsmXLdPz48aA2hmHoRz/6kdxut8aPH697771Xv/3tb4Pa9PX1qaysTJMmTdKECRNUUlKi06dPj/7dALJuWtRsiQkObVmSL0mDAhn//S1L8pnUC1iUmdlWq2ZuQwpiGhsbtXr1ajU3N6u+vl6XLl1SUVGRLly4EGjzwgsv6KWXXtLrr7+ujz76SC6XSwsXLtT58+cDbcrLy1VTU6Pq6mo1NTWpu7tbixcv1sDAgHnvzCTxPKfCqpjQ+ieLCnK0/dE75HIG/+FxOVO1/dE74mJYDbArM7OtVs3cOgzDCPus/Ic//EFZWVlqbGzU3LlzZRiG3G63ysvLtXHjRkmXsy7Z2dnaunWrnnrqKXm9Xk2ePFm7du3SihUrJElnzpxRXl6e3n77bRUXF4/4ul1dXXI6nfJ6vUpPTw/38EcU73MqrGr/kS/1D9VHRmz3ykMztXTmDWN/QDGAir2APfmHziUFZZ/93+5QfqyYua/hmH3+HtWcGK/XK0nKyLgcmbW3t8vj8aioqCjQJiUlRfPmzdPhw4clSS0tLerv7w9q43a7VVBQEGhztb6+PnV1dQXdxhpzKqzLqmnRsZSY4NCcaZlaOvMGzZmWSQAD2ISZ2VYrZm7DvjrJMAytXbtWhYWFKigokCR5PB5JUnZ2dlDb7Oxsff7554E2ycnJmjhx4qA2/udfrbKyUhUVFeEeasgoEmZt/rSox9s75P+hQ5e/lLGWFgWAcCwqyNHCfJcp2VYz9xUJYQcxpaWlOnr0qJqamgY95nAEv1nDMAZtu9q12mzatElr164N3O/q6lJeXl4YR319rHqpGS7zT2hdVdUqh4ZOizKhFYCd+LOtsbavsRbWcFJZWZlqa2t16NAh5ebmBra7XC5JGpRR6ezsDGRnXC6XLl68qHPnzg3b5mopKSlKT08Puo0lq15qhj+xYloUABCakDIxhmGorKxMNTU1amho0NSpU4Menzp1qlwul+rr6/UXf/EXkqSLFy+qsbFRW7dulSTNmjVL48aNU319vZYvXy5J6ujoUFtbm1544QUz3tOoMafCHqyWFgUAhCakIGb16tXavXu39u/fr7S0tEDGxel0avz48XI4HCovL9dzzz2nm266STfddJOee+45fe1rX9MjjzwSaLty5UqtW7dOmZmZysjI0Pr16zV9+nQtWLDA/HcYBuZU2IeV0qIAgNCEFMRs375dknTvvfcGbd+xY4eeeOIJSdIPf/hD9fT06Omnn9a5c+d011136Z133lFaWlqg/csvv6ykpCQtX75cPT09mj9/vnbu3KnExMTRvRuTMKcCAIDYN6o6MdFCnRgAgNXFY/0ms8/fLAB5DcypAACMBX4km4NMDAAAEeQvpnr1ydfMyrixKqYq9mLssXYTANgHC9Sai+GkGEa6EQDshWKq5iITE6NYuwkA7IdiquYiiIlBpBsBwJ4opmougpgYFEq6EQgX862AyPMXUx3uGleHLk8boJjq9WFOTAwi3YixxnwrIDoopmouMjExiHQjxhLzrYDoYoFa85CJiUGs3YSxMtJ8K4cuz7damO/ilyAwhiimag4yMTHIn26UNGjclHQjRoP5VkDs8C9Qu3TmDZozLZO/6WEgiIlRpBsxFphvBcBOGE6KYaQbYTbmWwGwE4KYGOdPNwJmYL4VADthOAmII8y3AmAnBDEjoCAY7Ib5VgDsguGka6AgGOyK+VYA7MBhGIblUgtdXV1yOp3yer1KT08fk9fwFwS7unP8f+L5xQoAQGjMPn8znDQEFmAEACD2EcQMgYJgAADEPoKYIVAQDACA2EcQMwQKggEAEPsIYobgLwg23HUaDl2+SomCYAAARA9BzBAoCAYAQOwjiBkGBcEAAHZn9YKuFLu7BgqCAQDsyg4FXSl2BwBAnIlWQVeK3dmc1VN7AIDYZqeCrgwnxRA7pPYAALEtlIKuc6ZlRu7AwkAmJkb4U3tXf7A83l6tqmpVXVtHlI4MAGAndiroShATA+yU2gMAxDY7FXQliIkBrNUEAIgUOxV0JYiJAXZK7QEAYpudCroSxMQAO6X2AACxzy4FXUMOYt577z0tWbJEbrdbDodD+/btC3q8u7tbpaWlys3N1fjx43Xrrbdq+/btQW36+vpUVlamSZMmacKECSopKdHp06dH9UaszE6pPQCANSwqyFHTxvu158m79cpDM7XnybvVtPF+ywQwUhhBzIULFzRjxgy9/vrrQz6+Zs0a1dXVqaqqSp999pnWrFmjsrIy7d+/P9CmvLxcNTU1qq6uVlNTk7q7u7V48WINDAyE/04szE6pPQCAdSQmODRnWqaWzrxBc6ZlWu48M6qKvQ6HQzU1NVq2bFlgW0FBgVasWKHNmzcHts2aNUvf/va39eMf/1her1eTJ0/Wrl27tGLFCknSmTNnlJeXp7ffflvFxcUjvq4VKvYO+IyQlyugTgwAwM7MPn+bXuyusLBQtbW1+t73vie3262GhgadOHFCr7zyiiSppaVF/f39KioqCjzH7XaroKBAhw8fHjKI6evrU19fX+B+V1eX2YdtqnCDEdZqAgDg+pk+sffVV19Vfn6+cnNzlZycrEWLFmnbtm0qLCyUJHk8HiUnJ2vixIlBz8vOzpbH4xlyn5WVlXI6nYFbXl6e2YdtmtEWrbN6ag8AgEgZkyCmublZtbW1amlp0U9/+lM9/fTTOnjw4DWfZxiGHI6hT9ibNm2S1+sN3E6dOmX2YZuConUAAESOqcNJPT09evbZZ1VTU6MHHnhAknT77bfryJEjevHFF7VgwQK5XC5dvHhR586dC8rGdHZ26p577hlyvykpKUpJSTHzUMeEndajAAAg1pmaienv71d/f78SEoJ3m5iYKJ/PJ+nyJN9x48apvr4+8HhHR4fa2tqGDWKsgqJ1AABETsiZmO7ubv3+978P3G9vb9eRI0eUkZGhG2+8UfPmzdOGDRs0fvx4TZkyRY2NjfrlL3+pl156SZLkdDq1cuVKrVu3TpmZmcrIyND69es1ffp0LViwwLx3FgUUrQMAIHJCDmI+/vhj3XfffYH7a9eulSQ9/vjj2rlzp6qrq7Vp0yb97d/+rc6ePaspU6bon//5n/X9738/8JyXX35ZSUlJWr58uXp6ejR//nzt3LlTiYmJJryl6PEXrfN4e4ecF+PQ5WqIFK0DAGD0RlUnJlpiuU6M/+okSUGBjH/KspXKOQMAYCazz9+snWQyu6xHAQBArDO92B0oWgcAQCQQxIwRf9E6AAAwNhhOAgAAlkQmBpYQzoKaAAB7I4hBzGN1bwDAUBhOQkwb7YKaAAD7IohBzGJBTSB6BnyGPjj5lfYf+VIfnPyK7xliEsNJiFksqAlEB0O4sAoyMYhZLKgJRB5DuLASghjELBbUBCKLIVxYDUEMYpZ/Qc3hLqR26HKKmwU1AXOEMoQLxAKCGMSsxASHtizJl6RBgYz//pYl+dSLAUzCEC6shiAGMY0FNa2JK1usiSFcWA1XJyHmsaCmtXBli3X5h3A93t4h58U4dPkHBEO4iBVkYmAJ/gU1l868QXOmZRLAxCiubLE2hnBhNQQxAEzBlS32wBAurIThJACmoDihfTCEC6sgiAFgCq5ssRf/EC4QyxhOAmAKrmwBEGkEMQBMQXFCAJFGEAPAFFzZAiDSCGIAmIYrWwBEEhN7AZiKK1sARApBDADTcWULgEggiIkjAz6DX8dAlPE9BMxDEBMnWM8GiD6+h4C5mNgbB1jPBog+voeA+QhibI71bIDo43sIjA2CGJsLZT0bAGOD7yEwNghibI71bIDo43sIjA2CGJtjPRsg+vgeAmODIMbmWM8GiD6+h8DYIIixOdazAaKP7yEwNghi4gDr2QDRx/cQMJ/DMIyQrul777339JOf/EQtLS3q6OhQTU2Nli1bFtTms88+08aNG9XY2Cifz6fbbrtN//7v/64bb7xRktTX16f169drz5496unp0fz587Vt2zbl5uZe1zF0dXXJ6XTK6/UqPT09lMOPa1QKBaKP7yHimdnn75AzMRcuXNCMGTP0+uuvD/n4yZMnVVhYqG9961tqaGjQp59+qs2bNys19U+/PsrLy1VTU6Pq6mo1NTWpu7tbixcv1sDAQPjvBCPyr2ezdOYNmjMtkz+cQBTwPQTME3ImJujJDsegTMxDDz2kcePGadeuXUM+x+v1avLkydq1a5dWrFghSTpz5ozy8vL09ttvq7i4eMTXJRMDAID1RD0Tcy0+n09vvfWWbr75ZhUXFysrK0t33XWX9u3bF2jT0tKi/v5+FRUVBba53W4VFBTo8OHDQ+63r69PXV1dQTcAABDfTA1iOjs71d3dreeff16LFi3SO++8owcffFDf+c531NjYKEnyeDxKTk7WxIkTg56bnZ0tj8cz5H4rKyvldDoDt7y8PDMPGwAAWJDpmRhJWrp0qdasWaOZM2fqmWee0eLFi/XGG29c87mGYcjhGHpseNOmTfJ6vYHbqVOnzDxsAABgQaYGMZMmTVJSUpLy8/ODtt9666364osvJEkul0sXL17UuXPngtp0dnYqOzt7yP2mpKQoPT096AYAAOKbqUFMcnKyZs+erePHjwdtP3HihKZMmSJJmjVrlsaNG6f6+vrA4x0dHWpra9M999xj5uEAAAAbSwr1Cd3d3fr9738fuN/e3q4jR44oIyNDN954ozZs2KAVK1Zo7ty5uu+++1RXV6cDBw6ooaFBkuR0OrVy5UqtW7dOmZmZysjI0Pr16zV9+nQtWLDAtDcGAADsLeRLrBsaGnTfffcN2v74449r586dkqRf/OIXqqys1OnTp3XLLbeooqJCS5cuDbTt7e3Vhg0btHv37qBid9c7YZdLrAEAsB6zz9+jqhMTLQQxAABYT0zXiQEAAIgUghgAAGBJBDEAAMCSCGIAAIAlhXyJNQAAVjPgM/Rh+1l1nu9VVlqq7pyawQriw7BSXxHEAABsra6tQxUHjqnD2xvYluNM1ZYl+VpUkBPFI4s9VusrhpMAALZV19ahVVWtQSdlSfJ4e7WqqlV1bR1ROrLYY8W+IogBANjSgM9QxYFjGqoYmn9bxYFjGvBZrlya6azaVwQxAABb+rD97KCswpUMSR3eXn3YfjZyBxWjrNpXBDEAAFvqPD/8STmcdnZm1b5iYi+AmGalKyUQW7LSUk1tZ2dW7SuCGAAxy2pXSiC23Dk1QznOVHm8vUPO9XBIcjkvB8bxzqp9xXASgJhkxSslEFsSExzasiRf0uWT8JX897csySezJ+v2FUEMgJhj1SslEHsWFeRo+6N3yOUMHgZxOVO1/dE7yOhdwYp9xXASgJgTypUSc6ZlRu7AYEmLCnK0MN/F3KrrYLW+IogBEHOseqUEYldigoOA9zpZqa8YTgIQc6x6pQSAyCKIARBz/FdKDJfAdujyVUqxdqUEgMgiiAEQc6x6pQSAyCKIARCTrHilBIDIYmIvgJhltSslAEQWQQyAmGalKyUARBbDSQAAwJIIYgAAgCURxAAAAEsiiAEAAJZEEAMAACyJIAYAAFgSQQwAALAkghgAAGBJBDEAAMCSLFmx1zAMSVJXV1eUjwQAAFwv/3nbfx4fLUsGMefPn5ck5eXlRflIAABAqM6fPy+n0znq/TgMs8KhCPL5fDpz5ozS0tLkcJi7EFxXV5fy8vJ06tQppaenm7pvDI9+jw76PTro9+ig36Pjyn5PS0vT+fPn5Xa7lZAw+hktlszEJCQkKDc3d0xfIz09nQ95FNDv0UG/Rwf9Hh30e3T4+92MDIwfE3sBAIAlEcQAAABLIoi5SkpKirZs2aKUlJRoH0pcod+jg36PDvo9Ouj36BjLfrfkxF4AAAAyMQAAwJIIYgAAgCURxAAAAEsiiAEAAJYUF0HMe++9pyVLlsjtdsvhcGjfvn1BjxuGoR/96Edyu90aP3687r33Xv32t78NatPX16eysjJNmjRJEyZMUElJiU6fPh3Bd2E91+r3/v5+bdy4UdOnT9eECRPkdrv13e9+V2fOnAnaB/0eupE+71d66qmn5HA49LOf/SxoO/0euuvp988++0wlJSVyOp1KS0vT3XffrS+++CLwOP0eupH6vbu7W6WlpcrNzdX48eN16623avv27UFt6PfQVFZWavbs2UpLS1NWVpaWLVum48ePB7WJ1Hk1LoKYCxcuaMaMGXr99deHfPyFF17QSy+9pNdff10fffSRXC6XFi5cGFijSZLKy8tVU1Oj6upqNTU1qbu7W4sXL9bAwECk3oblXKvf//jHP6q1tVWbN29Wa2ur9u7dqxMnTqikpCSoHf0eupE+73779u3Tr3/9a7nd7kGP0e+hG6nfT548qcLCQn3rW99SQ0ODPv30U23evFmpqamBNvR76Ebq9zVr1qiurk5VVVX67LPPtGbNGpWVlWn//v2BNvR7aBobG7V69Wo1Nzervr5ely5dUlFRkS5cuBBoE7HzqhFnJBk1NTWB+z6fz3C5XMbzzz8f2Nbb22s4nU7jjTfeMAzDMP73f//XGDdunFFdXR1o8+WXXxoJCQlGXV1dxI7dyq7u96F8+OGHhiTj888/NwyDfjfDcP1++vRp44YbbjDa2tqMKVOmGC+//HLgMfp99Ibq9xUrVhiPPvrosM+h30dvqH6/7bbbjP/3//5f0LY77rjD+Kd/+ifDMOh3M3R2dhqSjMbGRsMwIntejYtMzLW0t7fL4/GoqKgosC0lJUXz5s3T4cOHJUktLS3q7+8PauN2u1VQUBBog9Hzer1yOBz6+te/Lol+Hys+n0+PPfaYNmzYoNtuu23Q4/S7+Xw+n9566y3dfPPNKi4uVlZWlu66666goQ/6fWwUFhaqtrZWX375pQzD0KFDh3TixAkVFxdLot/N4PV6JUkZGRmSIntejfsgxuPxSJKys7ODtmdnZwce83g8Sk5O1sSJE4dtg9Hp7e3VM888o0ceeSSwMBv9Pja2bt2qpKQk/eAHPxjycfrdfJ2dneru7tbzzz+vRYsW6Z133tGDDz6o73znO2psbJREv4+VV199Vfn5+crNzVVycrIWLVqkbdu2qbCwUBL9PlqGYWjt2rUqLCxUQUGBpMieVy25ivVYcDgcQfcNwxi07WrX0wYj6+/v10MPPSSfz6dt27aN2J5+D19LS4teeeUVtba2htyH9Hv4fD6fJGnp0qVas2aNJGnmzJk6fPiw3njjDc2bN2/Y59Lvo/Pqq6+qublZtbW1mjJlit577z09/fTTysnJ0YIFC4Z9Hv1+fUpLS3X06FE1NTUNeiwS59W4z8S4XC5JGhT5dXZ2BqJIl8ulixcv6ty5c8O2QXj6+/u1fPlytbe3q76+PpCFkej3sfD++++rs7NTN954o5KSkpSUlKTPP/9c69at0ze+8Q1J9PtYmDRpkpKSkpSfnx+0/dZbbw1cnUS/m6+np0fPPvusXnrpJS1ZskS33367SktLtWLFCr344ouS6PfRKCsrU21trQ4dOqTc3NzA9kieV+M+iJk6dapcLpfq6+sD2y5evKjGxkbdc889kqRZs2Zp3LhxQW06OjrU1tYWaIPQ+QOY3/3udzp48KAyMzODHqffzffYY4/p6NGjOnLkSODmdru1YcMG/epXv5JEv4+F5ORkzZ49e9BlqCdOnNCUKVMk0e9job+/X/39/UpICD7VJSYmBrJj9HvoDMNQaWmp9u7dq3fffVdTp04Nejyi59XRzEi2ivPnzxuffPKJ8cknnxiSjJdeesn45JNPAlfBPP/884bT6TT27t1r/OY3vzEefvhhIycnx+jq6grs4/vf/76Rm5trHDx40GhtbTXuv/9+Y8aMGcalS5ei9bZi3rX6vb+/3ygpKTFyc3ONI0eOGB0dHYFbX19fYB/0e+hG+rxf7eqrkwyDfg/HSP2+d+9eY9y4cca//Mu/GL/73e+M1157zUhMTDTef//9wD7o99CN1O/z5s0zbrvtNuPQoUPGf//3fxs7duwwUlNTjW3btgX2Qb+HZtWqVYbT6TQaGhqC/nb/8Y9/DLSJ1Hk1LoKYQ4cOGZIG3R5//HHDMC5fDrZlyxbD5XIZKSkpxty5c43f/OY3Qfvo6ekxSktLjYyMDGP8+PHG4sWLjS+++CIK78Y6rtXv7e3tQz4myTh06FBgH/R76Eb6vF9tqCCGfg/d9fT7m2++aXzzm980UlNTjRkzZhj79u0L2gf9HrqR+r2jo8N44oknDLfbbaSmphq33HKL8dOf/tTw+XyBfdDvoRnub/eOHTsCbSJ1XnX83wEBAABYStzPiQEAANZEEAMAACyJIAYAAFgSQQwAALAkghgAAGBJBDEAAMCSCGIAAIAlEcQAAABLIogBAACWRBADAAAsiSAGAABYEkEMAACwpP8PR7cS8CGkwMcAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "## 绘图\n",
    "import numpy as np\n",
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "N = 50\n",
    "x = np.random.rand(N)\n",
    "y = np.random.rand(N)\n",
    "\n",
    "x_t = [int(x_pt) + int(np.random.randint(2*N)) + 2*N for x_pt in x]\n",
    "y_t = [int(y_pt) + int(np.random.randint(3*N)) + 3*N for y_pt in y]\n",
    "\n",
    "plt.scatter(x_t, y_t)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "a68a95c2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAigAAAGgCAYAAACABpytAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8pXeV/AAAACXBIWXMAAA9hAAAPYQGoP6dpAAAunElEQVR4nO3de3BU533G8Wd1J1TaImG02iBc1bWdKMJ4IMaBoTGY+xiB6+n4Vqd0ykxcbKixgdjEk8HMpJbJtHaSoeDWdUOChqp/1GDTpgryYCAMUECyamQ8vhCVCNitpkBWEkFC2T39Q9GGtSS0Kx2dfc/Z72dmZ6LdI/ndk7NnH97L7/VZlmUJAADAIFnpbgAAAMDnEVAAAIBxCCgAAMA4BBQAAGAcAgoAADAOAQUAABiHgAIAAIxDQAEAAMYhoAAAAOMQUAAAgHFSCig1NTW65557VFhYqEmTJunBBx/Uxx9/nHCMZVl66aWXFAwGNW7cOM2dO1cffvhhwjE9PT1au3atJk6cqPHjx2v58uU6f/786N8NAADwBF8qe/EsWbJEjz76qO655x795je/0YsvvqjTp0/rzJkzGj9+vCRp69at+pu/+Rvt3LlTd9xxh7773e/q8OHD+vjjj1VYWChJWr16tfbt26edO3eqpKRE69ev1+XLl9XY2Kjs7Oxh2xGLxXTx4kUVFhbK5/ON8K0DAAAnWZalzs5OBYNBZWUN00dijUJ7e7slyTp06JBlWZYVi8WsQCBgvfLKK/Fjuru7Lb/fb73++uuWZVnWr371Kys3N9eqq6uLH3PhwgUrKyvLqq+vT+q/29bWZkniwYMHDx48eLjw0dbWNux3fY5GIRKJSJKKi4slSa2trQqHw1q0aFH8mPz8fN133306evSonnzySTU2Nqq3tzfhmGAwqKqqKh09elSLFy8e8N/p6elRT09P/Gfrt50+bW1tKioqGs1bAAAADuno6FB5eXl8ROVmRhxQLMvSc889pzlz5qiqqkqSFA6HJUmlpaUJx5aWlurcuXPxY/Ly8jRhwoQBx/T//ufV1NRoy5YtA54vKioioAAA4DLJTM8Y8SqeNWvW6IMPPtC//Mu/DPsftixr2Mbc7JhNmzYpEonEH21tbSNtNgAAcIERBZS1a9fqnXfe0XvvvafJkyfHnw8EApI0oCekvb093qsSCAR0/fp1XblyZchjPi8/Pz/eW0KvCQAA3pdSQLEsS2vWrNFbb72lAwcOqKKiIuH1iooKBQIBNTQ0xJ+7fv26Dh06pNmzZ0uSZsyYodzc3IRjQqGQWlpa4scAAIDMltIclKefflq7d+/W22+/rcLCwnhPid/v17hx4+Tz+bRu3Tq9/PLLuv3223X77bfr5Zdf1he+8AU9/vjj8WNXrVql9evXq6SkRMXFxdqwYYOmTp2qBQsW2P8OAQCA66QUUHbs2CFJmjt3bsLzP/rRj/QXf/EXkqRvfetbunbtmp566ilduXJF9957r/bv358wY/e1115TTk6OHn74YV27dk3z58/Xzp07k6qBAgAAvC+lQm2m6OjokN/vVyQSYT4KAAAukcr3N3vxAAAA4xBQAACAcUZVSTYTRWOWTrReVntntyYVFmhmRbGys9gPCGOHaw5exvWNoRBQUlDfEtKWfWcUinTHnyvzF2hzdaWWVJWlsWXwKq45eBnXN26GIZ4k1beEtLq2KeGDJEnhSLdW1zapviWUppbBq7jm4GVc3xgOASUJ0ZilLfvOaLDlTv3Pbdl3RtGY6xZEwVBcc/Ayrm8kg4CShBOtlwek/BtZkkKRbp1ovexcozwgGrN07Owlvd18QcfOXuJmdAOuOXgZ1/fvcB8cGnNQktDeOfQHaSTHgbHn4XDNwcu4vvtwH7w5elCSMKmwwNbjMh1jz8PjmoOXcX1zH0wGASUJMyuKVeYv0FAL33zqS70zK4qdbJYrMfacHK45eFmmX9/cB5NDQElCdpZPm6srJWnAB6r/583VlazdTwJjz8nhmoOXZfr1zX0wOQSUJC2pKtOOJ6Yr4E/scgz4C7TjiemMFyaJsefkcc3ByzL5+uY+mBwmyaZgSVWZFlYGqHo4Cow9p4ZrDl6Wqdc398HkEFBSlJ3l06zbStLdDNfqH3sOR7oHHX/1qe9fUF4dex4Jrjl4WSZe39wHk8MQDxyV6WPPAMB9MDkEFDguk8eeAUDiPpgMn2VZrlvH1NHRIb/fr0gkoqKionQ3ByOU6buYZvr7B5B594FUvr+Zg4K0ycSx535UkAQgZfZ9cDgM8QAOo4IkAAyPgAI4iAqSAJAcAgrgICpIAkByCCiAg6ggCQDJIaAADqKCJAAkh4ACOCjTd3EFgGQRUAAHUUESAJJDQAEcRgVJABgehdqANMjUXVwBIFkEFCBNTKwgaWfZ7Uwr4Q2kkxc/bwQUAJLsLb9PKX/AOV79vDEHBYCt5fcp5Q84x8ufNwIKcINozNKxs5f0dvMFHTt7KSNKzttZfp9S/oBzvP55Y4gH+C2vdpMOJ5Xy+8PNmbHzbwG4Oa9/3uhBAeTtbtLh2Fl+n1L+gHO8/nkjoCDjeb2bdDh2lt+nlD/gHK9/3ggoyHiZvsOwneX3KeUPOMfrnzcCCjKe17tJh2Nn+X1K+QPO8frnjYCCjOf1btJk2Fl+n1L+gHO8/HnzWZbluoH1jo4O+f1+RSIRFRUVpbs5cLlozNKcrQcUjnQPOg/Fp74P+5Hn73ftv0SSRSVZ2IX//53llvOdyvc3y4yR8fq7SVfXNsknJYQUL3STpsLO8vsmlvKHMzJ1yX46efHzxhAPIG93kwJOyuQl+7AXPSjAb7HDMDA6wy3Z96lvyf7CygCfKwyLgALcwIvdpIBTvF7ZFM5iiAcAYItMX7IPexFQAAC2YMk+7ERAAQDYwuuVTeEsAgoAwBZer2wKZxFQAAC2Yck+7MIqHgCArViyDzsQUIAMYVcpbLeU1EZ6sWQfo0VAATKAXaXHKWEOwCnMQQE8zq7S45QwB+AkAgrgYcOVHpf6So9HYzff1NyuvwOMlWjM0rGzl/R28wUdO3uJa9EDGOIBPMyu0uOUMIfJGHr0JnpQAA+zq/Q4JcxhKoYevYuAAniYXaXHKWEOEzH06G0EFMDD7Co9TglzmCiVoUe7Medl7DEHBfCw/tLjq2ub5JMS/qWZSulxu/4OYKd0DT0y58UZ9KAAHmdX6XFKmMM06Rh6ZM6Lc+hBGQNU2oRp7Co9TglzSObc4/qHHsOR7kHnofjUF6DtGnocbs6LT31zXhZWBvhM2CDlHpTDhw+rurpawWBQPp9Pe/fuTXi9q6tLa9as0eTJkzVu3Dh9+ctf1o4dOxKO6enp0dq1azVx4kSNHz9ey5cv1/nz50f1RkxR3xLSnK0H9Ngbx/VMXbMee+O45mw9QKpG2vWXHl9x9xc167aSEd9A7fo7cCeT7nFO756czjkvmSjlgHL16lVNmzZN27ZtG/T1Z599VvX19aqtrdVHH32kZ599VmvXrtXbb78dP2bdunXas2eP6urqdOTIEXV1dWnZsmWKRqMjfycGoOsPgJeZeI9zcuiR5fbOSnmIZ+nSpVq6dOmQrx87dkwrV67U3LlzJUnf/OY39Q//8A86deqUVqxYoUgkojfffFO7du3SggULJEm1tbUqLy/Xu+++q8WLF4/snaQZXX8AvMzke5xTQ48st3eW7ZNk58yZo3feeUcXLlyQZVl677339Mknn8SDR2Njo3p7e7Vo0aL47wSDQVVVVeno0aOD/s2enh51dHQkPExD1x8ALzP9HufE0CPL7Z1le0D54Q9/qMrKSk2ePFl5eXlasmSJtm/frjlz5kiSwuGw8vLyNGHChITfKy0tVTgcHvRv1tTUyO/3xx/l5eV2N3vU6PoD4GXc45yf85LpxiSgHD9+XO+8844aGxv1d3/3d3rqqaf07rvv3vT3LMuSzzf4/6mbNm1SJBKJP9ra2uxu9qjR9QfAy7jH9WG5vXNsXWZ87do1ffvb39aePXv0wAMPSJLuuusuNTc362//9m+1YMECBQIBXb9+XVeuXEnoRWlvb9fs2bMH/bv5+fnKz8+3s6m2c3q5GwA4iXvc77Dc3hm29qD09vaqt7dXWVmJfzY7O1uxWEySNGPGDOXm5qqhoSH+eigUUktLy5ABxQ3o+gPgZdzjErHcfuyl3IPS1dWlzz77LP5za2urmpubVVxcrClTpui+++7Txo0bNW7cON166606dOiQfvKTn+jVV1+VJPn9fq1atUrr169XSUmJiouLtWHDBk2dOjW+qset+rv+Pl8COUAJZAAewD0OTvJZlpXSDkcHDx7UvHnzBjy/cuVK7dy5U+FwWJs2bdL+/ft1+fJl3XrrrfrmN7+pZ599Nj7HpLu7Wxs3btTu3bt17do1zZ8/X9u3b0968mtHR4f8fr8ikYiKiopSab4jTKmyCABjgXscRiqV7++UA4oJTA8oANyLL1+YxkvXZCrf3+zFAwC/xS61ME0mX5PsZgwAMrOMOzJbpl+TBBQAGW+4Mu5SXxn3aMx1I+JwKa5JAgoAGF/GHZmHa5KAAgCUcYdxuCYJKABAGXcYh2uSgAIAntilNhqzdOzsJb3dfEHHzl7y9NyETOCFa3K0WGYMIOP1l3FfXdskn5QwMdENZdwzeSmqV7n9mrQDPSgAIPfuUpvpS1G9zK3XpF2oJAsAN3BT1c5ozNKcrQeGXO3Rv8PwkefvN/Y9YHhuuiaHQyVZABih/l1q3SCVpahueU8YyE3XpJ0Y4gEAl2IpKryMgAIALsVSVHgZAQUAXIqlqPAyAgoAuFT/UlRJA0JKpixFhXcRUADAxTJ9KSq8i1U8AOByS6rKtLAy4JmlqIBEQAEAT8jUpajwLoZ4AACAcQgoAADAOAQUAABgHAIKAAAwDgEFAAAYh4ACAACMQ0ABAADGIaAAAADjEFAAAIBxqCSbIaIxizLYAADXIKBkgPqWkLbsO6NQpDv+XJm/QJurK9lIDABgJIZ4PK6+JaTVtU0J4USSwpFura5tUn1LKE0tAwBgaAQUD4vGLG3Zd0bWIK/1P7dl3xlFY4MdAQBA+hBQPOxE6+UBPSc3siSFIt060XrZuUYBAJAEAoqHtXcOHU5GchwAAE4hoHjYpMICW48DAMApBBQPm1lRrDJ/gYZaTOxT32qemRXFTjYLAIBhEVA8LDvLp83VlZI0IKT0/7y5upJ6KAAA4xBQPG5JVZl2PDFdAX/iME7AX6AdT0ynDgoAwEgUassAS6rKtLAyQCVZAIBrEFAyRHaWT7NuK0l3MwAASApDPAAAwDgEFAAAYBwCCgAAMA4BBQAAGIeAAgAAjENAAQAAxiGgAAAA4xBQAACAcQgoAADAOAQUAABgHAIKAAAwDgEFAAAYh80CAQAZIRqz2NXdRQgoAADPq28Jacu+MwpFuuPPlfkLtLm6UkuqytLYMgyFIR4AgKfVt4S0urYpIZxIUjjSrdW1TapvCaWpZbgZAgoAwLOiMUtb9p2RNchr/c9t2XdG0dhgRyCdCCgAAM860Xp5QM/JjSxJoUi3TrRedq5RSAoBBQDgWe2dQ4eTkRwH5xBQAACeNamwwNbj4BxW8aQJy90AYOzNrChWmb9A4Uj3oPNQfJIC/r57MMyScg/K4cOHVV1drWAwKJ/Pp7179w445qOPPtLy5cvl9/tVWFior33ta/rlL38Zf72np0dr167VxIkTNX78eC1fvlznz58f1Rtxk/qWkOZsPaDH3jiuZ+qa9dgbxzVn6wFmkgOAzbKzfNpcXSmpL4zcqP/nzdWV/APRQCkHlKtXr2ratGnatm3boK+fPXtWc+bM0Ze+9CUdPHhQ//3f/63vfOc7Kij4XffZunXrtGfPHtXV1enIkSPq6urSsmXLFI1GR/5OXILlbgDgrCVVZdrxxHQF/InDOAF/gXY8MZ06KIbyWZY14rVVPp9Pe/bs0YMPPhh/7tFHH1Vubq527do16O9EIhHdcsst2rVrlx555BFJ0sWLF1VeXq6f/vSnWrx48bD/3Y6ODvn9fkUiERUVFY20+Y6LxizN2XpgyBnl/V2NR56/nzQPADZjaD39Uvn+tnWSbCwW03/8x3/ojjvu0OLFizVp0iTde++9CcNAjY2N6u3t1aJFi+LPBYNBVVVV6ejRo4P+3Z6eHnV0dCQ83IjlbgCQPtlZPs26rUQr7v6iZt1WQjgxnK0Bpb29XV1dXXrllVe0ZMkS7d+/X3/yJ3+ihx56SIcOHZIkhcNh5eXlacKECQm/W1paqnA4POjframpkd/vjz/Ky8vtbLZjWO4GAEBybO9BkaQVK1bo2Wef1d13360XXnhBy5Yt0+uvv37T37UsSz7f4Gl206ZNikQi8UdbW5udzXYMy90AAEiOrQFl4sSJysnJUWVlZcLzX/7yl+OreAKBgK5fv64rV64kHNPe3q7S0tJB/25+fr6KiooSHm7Uv9xtqE5Fn/o2r2K5GwAg09kaUPLy8nTPPffo448/Tnj+k08+0a233ipJmjFjhnJzc9XQ0BB/PRQKqaWlRbNnz7azOcZhuRsAAMlJuVBbV1eXPvvss/jPra2tam5uVnFxsaZMmaKNGzfqkUce0de//nXNmzdP9fX12rdvnw4ePChJ8vv9WrVqldavX6+SkhIVFxdrw4YNmjp1qhYsWGDbGzNV/3K3z2/7HWDbbwAA4lJeZnzw4EHNmzdvwPMrV67Uzp07JUn//M//rJqaGp0/f1533nmntmzZohUrVsSP7e7u1saNG7V7925du3ZN8+fP1/bt25Oe/OrWZcY3YrkbACDTpPL9Pao6KOnihYACAECmSVsdFAAAADsQUAAAgHEIKAAAwDgEFAAAYBwCCgAAMA4BBQAAGIeAAgAAjENAAQAAxiGgAAAA46S8Fw8AwJ3YYgNuQkABgAxQ3xIasElpGZuUwmAM8QCAx9W3hLS6tikhnEhSONKt1bVNqm8JpallwNAIKADgYdGYpS37zmiwXWH7n9uy74yiMdftGwuPI6AASJtozNKxs5f0dvMFHTt7iS/JMXCi9fKAnpMbWZJCkW6daL3sXKOAJDAHBUBaMCfCGe2dQ4eTkRwHOIUeFACOY06EcyYVFth6HOAUAgoARzEnwlkzK4pV5i/QUIuJferruZpZUexks4BhEVAAOIo5Ec7KzvJpc3WlJA0IKf0/b66upB4KjENAAeAo5kQ4b0lVmXY8MV0Bf+IwTsBfoB1PTGfOD4zEJFkAjmJORHosqSrTwsoAlWThGgQUAI7qnxMRjnQPOg/Fp75/2TMnwn7ZWT7Nuq0k3c0AksIQDwBHMScCQDIIKAAcx5wIAMNhiAdAWjAnAsDNEFAApA1zIgAMhSEeAABgHAIKAAAwDkM8N4jGLMbDAQAwAAHlt9hZFQAAczDEI3ZWBQDANBkfUNhZFQAA82R8QGFnVQAAzJPxAYWdVQEAME/GBxR2VgUAwDwZH1D6d1YdajGxT32redhZFQAA52R8QGFnVQAAzJPxAUViZ1UAAExDobbfYmdVAADMQUC5ATurAgBgBoZ4AACAcQgoAADAOAzxeAC7MAMAvIaA4nLswgwA8CKGeFyMXZgBAF5FQHEpdmEGAHgZAcWl2IUZAOBlBBSXYhdmAICXEVBcil2YAQBeRkBxKXZhBgB4GQHFpdiFGQDgZQQUF2MXZgCAV1GozeXYhRkA4EUEFA9gF2YAgNcwxAMAAIxDQAEAAMYhoAAAAOMQUAAAgHEIKAAAwDis4oHrRWMWy6wBwGNS7kE5fPiwqqurFQwG5fP5tHfv3iGPffLJJ+Xz+fT9738/4fmenh6tXbtWEydO1Pjx47V8+XKdP38+1aYAqm8Jac7WA3rsjeN6pq5Zj71xXHO2HlB9SyjdTQMAjELKAeXq1auaNm2atm3bdtPj9u7dq//6r/9SMBgc8Nq6deu0Z88e1dXV6ciRI+rq6tKyZcsUjUZTbQ4yWH1LSKtrmxSKJO7YHI50a3VtEyEFAFws5SGepUuXaunSpTc95sKFC1qzZo1+9rOf6YEHHkh4LRKJ6M0339SuXbu0YMECSVJtba3Ky8v17rvvavHixak2CRkoGrO0Zd8ZWYO8ZqlvP6It+85oYWWA4R4AcCHbJ8nGYjF94xvf0MaNG/WVr3xlwOuNjY3q7e3VokWL4s8Fg0FVVVXp6NGjg/7Nnp4edXR0JDyQ2U60Xh7Qc3IjS1Io0q0TrZeda1QaRWOWjp29pLebL+jY2UuKxgaLbgDgHrZPkt26datycnL013/914O+Hg6HlZeXpwkTJiQ8X1paqnA4POjv1NTUaMuWLXY3FS7W3jl0OBnJcW5W3xLSln1nEgJbmb9Am6sr2TASgGvZ2oPS2NioH/zgB9q5c6d8vtS61S3LGvJ3Nm3apEgkEn+0tbXZ0Vy42KTCguEPSuE4t2IeDgCvsjWg/PznP1d7e7umTJminJwc5eTk6Ny5c1q/fr3+4A/+QJIUCAR0/fp1XblyJeF329vbVVpaOujfzc/PV1FRUcIDmW1mRbHK/AUaKgb71NeLMLOi2MlmOWq4eThS3zwchnsAuJGtAeUb3/iGPvjgAzU3N8cfwWBQGzdu1M9+9jNJ0owZM5Sbm6uGhob474VCIbW0tGj27Nl2Ngcelp3l0+bqSkkaEFL6f95cXenpCbLMwwHgZSnPQenq6tJnn30W/7m1tVXNzc0qLi7WlClTVFJSknB8bm6uAoGA7rzzTkmS3+/XqlWrtH79epWUlKi4uFgbNmzQ1KlT46t6gGQsqSrTjiemD5h/EciQ+RfMwwHgZSkHlFOnTmnevHnxn5977jlJ0sqVK7Vz586k/sZrr72mnJwcPfzww7p27Zrmz5+vnTt3Kjs7O9XmIMMtqSrTwspARlaSZR4OAC/zWZblugHqjo4O+f1+RSIR5qMgY0VjluZsPaBwpHvQeSg+9fUmHXn+/owIbADMl8r3N5sFAi7FPBwAXkZAAVysfx5OwJ84jBPwF2jHE9M9Pw8HgHexmzHgcpk8DwcwGTutjw4BBfCA7CyfZt1WMvyBABxBhefRY4gHAAAbUeHZHgQUAABsQoVn+zDEAwCIY97E6KRS4dnUYVlTrgECCgBAEvMm7OD2Cs8mXQMM8QAAmDdhEzdXeDbtGiCgAECGY96Efdy607qJ1wABBQAyHDtj28etFZ5NvAYIKACQ4dw+b8I0bqzwbOI1wCRZAMhwbp43YSq3VXg28RogoABAikxZhmmX/nkTw+2Mbdq8CdO5qcKzidcAAQUAUmDSMky79M+bWF3bJJ+U8AVl8rwJ2MfEa4A5KACQJNOWYdrJjfMmYC/TrgGfZVmuWzfW0dEhv9+vSCSioqKidDcHQJo5MeQSjVmas/XAkCsd+rvAjzx/v6t7Grw2fIXUjeU1kMr3N0M8AFzNqSEXL5QwT4ab5k1gbJhyDTDEA8C1nBxyMXEZJuBlBBQAruR05UsTl2ECXkZAAeBKTle+dGsJc8CtCCgAXMnpIRe3ljAH3IqAAsCV0jHkYtoyTMDLWMUDwJXSVfnSbSXMAbcioABwpXRWvjRlGSbgZQzxAHAthlwA76IHBYCrMeQCeBMBBYDrMeQCeA9DPAAAwDgEFAAAYBwCCgAAMA4BBQAAGIeAAgAAjENAAQAAxiGgAAAA4xBQAACAcQgoAADAOAQUAABgHAIKAAAwDgEFAAAYh4ACAACMw27GwBiIxiydaL2s9s5uTSos0MyKYmVn+dLdLABwDQIKYLP6lpC27DujUKQ7/lyZv0Cbqyu1pKosjS0DAPdgiAewUX1LSKtrmxLCiSSFI91aXduk+pZQmloGAO5CQAFsEo1Z2rLvjKxBXut/bsu+M4rGBjsCQ4nGLB07e0lvN1/QsbOXOH9AhmCIB7DJidbLA3pObmRJCkW6daL1smbdVuJcw1yM4TIgc9GDAtikvXPocDKS4zIdw2VAZiOgADaZVFhg63GZjOEyAAQUwCYzK4pV5i/QUIuJfeobnphZUexks1wpleEyr2MODjIVc1AAm2Rn+bS5ulKra5vkkxL+9d8fWjZXV1IPJQkMl/VhDg4yGT0ogI2WVJVpxxPTFfAnDuME/AXa8cR0vlSSxHAZc3AAelAQR/VTeyypKtPCygDnchT6h8vCke5B56H41Bf6vDpcNtwcHJ/65uAsrAxwXcGzCCiQRFey3bKzfCwlHoVMHy5jyTrAEA9EVzLMlMnDZczBAehByXh0JcNkmTpcxhwcgICS8ehKhukycbgs0+fgABJDPBmPrmTAPP1zcCQNqKuTCXNwAImAkvHoSgbMlMlzcACJIZ6MR1cyYK5MnYMDSCPoQTl8+LCqq6sVDAbl8/m0d+/e+Gu9vb16/vnnNXXqVI0fP17BYFB//ud/rosXLyb8jZ6eHq1du1YTJ07U+PHjtXz5cp0/f37UbwapoysZMFv/HJwVd39Rs24r4bOIjJFyQLl69aqmTZumbdu2DXjt17/+tZqamvSd73xHTU1Neuutt/TJJ59o+fLlCcetW7dOe/bsUV1dnY4cOaKuri4tW7ZM0Wh05O8EI0ZXMgDAND7Lska885TP59OePXv04IMPDnnMyZMnNXPmTJ07d05TpkxRJBLRLbfcol27dumRRx6RJF28eFHl5eX66U9/qsWLFw/73+3o6JDf71ckElFRUdFIm4/PoZIsAGAspfL9PeZzUCKRiHw+n37/939fktTY2Kje3l4tWrQofkwwGFRVVZWOHj06aEDp6elRT09P/OeOjo6xbnZGysTlnAAAM43pKp7u7m698MILevzxx+NJKRwOKy8vTxMmTEg4trS0VOFweNC/U1NTI7/fH3+Ul5ePZbMBAECajVlA6e3t1aOPPqpYLKbt27cPe7xlWfL5Bh9O2LRpkyKRSPzR1tZmd3MBAIBBxiSg9Pb26uGHH1Zra6saGhoSxpkCgYCuX7+uK1euJPxOe3u7SktLB/17+fn5KioqSngAAADvsj2g9IeTTz/9VO+++65KShLnNMyYMUO5ublqaGiIPxcKhdTS0qLZs2fb3RwAAOBCKU+S7erq0meffRb/ubW1Vc3NzSouLlYwGNSf/umfqqmpSf/+7/+uaDQan1dSXFysvLw8+f1+rVq1SuvXr1dJSYmKi4u1YcMGTZ06VQsWLLDvnQEAANdKeZnxwYMHNW/evAHPr1y5Ui+99JIqKioG/b333ntPc+fOldQ3eXbjxo3avXu3rl27pvnz52v79u1JT35lmTEAAO6Tyvf3qOqgpAsBBQAA90nl+5vNAgEAgHEIKAAAwDgEFAAAYBwCCgAAMA4BBQAAGIeAAgAAjDPmuxkDADAa0ZilE62X1d7ZrUmFBZpZUazsrMH3boN3EFAAAMaqbwlpy74zCkW648+V+Qu0ubpSS6rK0tgyjDWGeAAARqpvCWl1bVNCOJGkcKRbq2ubVN8SSlPL4AQCCgDAONGYpS37zmiwUuf9z23Zd0bRmOuKoSNJBBQAgHFOtF4e0HNyI0tSKNKtE62XnWsUHEVAAQAYp71z6HAykuPgPgQUAIBxJhUW2Hoc3IeAAgAwzsyKYpX5CzTUYmKf+lbzzKwodrJZcBABBQBgnOwsnzZXV0rSgJDS//Pm6krqoXgYAQUAYKQlVWXa8cR0BfyJwzgBf4F2PDGdOigeR6E2w1FBEUAmW1JVpoWVAe6DGYiAYjAqKAJA33DPrNtK0t0MOIwhHkNRQREAkMkIKAaigiIAINMRUAxEBUXAftGYpWNnL+nt5gs6dvYSAR8wHHNQDEQFRcBezOcC3IceFANRQRGwD/O5AHcioBiICoqAPdI5n4shJWB0GOIxUH8FxdW1TfJJCTdXKigCyUtlPpedy1gZUgJGjx4UQ1FBERi9dMznYkgJsAc9KAajgiIwOk7P5xpuSMmnviGlhZUBPsfAMAgohqOCIjBy/fO5wpHuQUODT329knbN50rXkBLgRQzxAPAsp3fEpUQAYB8CCgBPc3I+FyUCAPswxIOMwc7Qmcup+VxODykBXkZAQUZg2SecmM9FiQDAPgzxwPNY9gknUSIAsAc9KPA0ln0iHSgRAIweAQVjwpT5Hiz7RLpQIsCdTLl3gYCCMWDSfA+WfQJIlkn3LjAHBTYzbb4Hyz4BJMO0excIKLBROneOHQo7QwMYjon3LhBQYKNU5ns4xelKogDcx8R7FwgosJGp8z1Y9gngZky9d2U6JsnCNibP92DZJ4ChmHzvymQEFNjG9DLfLPsEMBjT712ZiiEe2Ib5HgDciHuXmQgosBXzPQC4Efcu8/gsy3LduqmOjg75/X5FIhEVFRWluzkZJ5lKi1RjBOBGXr93pfv9pfL9zRwUpCTZSovM9wDgRl6+d7mtUi5DPEgalRYBwJ3ceP8moCApVFoEAHdy6/2bgIKkUGkRANzJrfdvAgqSQqVFAHAnt96/CShICpUWAcCd3Hr/JqAgKewKDADu5Nb7NwEFSaHSIgC4k1vv3wQUJI1KiwDgTm68f1NJFilLdyVCAMDIpPv+TSVZjCknKy2m+8PkljYBQDLcVCmXgAJjmViW2cQ2AYAXMQcFRjKxLLOJbQIAryKgwDgmlmU2sU1wv2jM0rGzl/R28wUdO3uJ6we4QcoB5fDhw6qurlYwGJTP59PevXsTXrcsSy+99JKCwaDGjRunuXPn6sMPP0w4pqenR2vXrtXEiRM1fvx4LV++XOfPnx/VG4F3mFiW2cQ2wd3qW0Kas/WAHnvjuJ6pa9ZjbxzXnK0H6IkDfivlgHL16lVNmzZN27ZtG/T1733ve3r11Ve1bds2nTx5UoFAQAsXLlRnZ2f8mHXr1mnPnj2qq6vTkSNH1NXVpWXLlikajY78ncAzTCzLbGKb4F4MFwLDS3mS7NKlS7V06dJBX7MsS9///vf14osv6qGHHpIk/fjHP1Zpaal2796tJ598UpFIRG+++aZ27dqlBQsWSJJqa2tVXl6ud999V4sXLx7F24EXmFiW2cQ2wZ2GGy70qW+4cGFlgNVhyGi2zkFpbW1VOBzWokWL4s/l5+frvvvu09GjRyVJjY2N6u3tTTgmGAyqqqoqfszn9fT0qKOjI+EB7zKxLLOJbYI7MVwIJMfWgBIOhyVJpaWlCc+XlpbGXwuHw8rLy9OECROGPObzampq5Pf744/y8nI7mw3DmFiW2cQ2wZ0YLgSSMyareHy+xJu0ZVkDnvu8mx2zadMmRSKR+KOtrc22tsJMJpZlNrFNcB+GC4Hk2FqoLRAISOrrJSkr+93Nur29Pd6rEggEdP36dV25ciWhF6W9vV2zZ88e9O/m5+crPz/fzqbCBZZUlWlhZcCoqq0mtgnu0j9cGI50DzoPxae+0MtwITKdrT0oFRUVCgQCamhoiD93/fp1HTp0KB4+ZsyYodzc3IRjQqGQWlpahgwoyFz9ZZlX3P1FzbqtxIggYGKb4B4MFwLJSbkHpaurS5999ln859bWVjU3N6u4uFhTpkzRunXr9PLLL+v222/X7bffrpdffllf+MIX9Pjjj0uS/H6/Vq1apfXr16ukpETFxcXasGGDpk6dGl/VAwBe1j9c+PltEwJsmwDEpRxQTp06pXnz5sV/fu655yRJK1eu1M6dO/Wtb31L165d01NPPaUrV67o3nvv1f79+1VYWBj/nddee005OTl6+OGHde3aNc2fP187d+5Udna2DW8JAMzHcCFwcz7LslxXWzmV7ZoBAIAZUvn+Zi8eAABgHAIKAAAwDgEFAAAYh4ACAACMQ0ABAADGIaAAAADjEFAAAIBxCCgAAMA4BBQAAGAcW3czdkp/8duOjo40twQAACSr/3s7mSL2rgwonZ2dkqTy8vI0twQAAKSqs7NTfr//pse4ci+eWCymixcvqrCwUD5f8htrdXR0qLy8XG1tbezh4wDOt7M4387ifDuL8+2ssTrflmWps7NTwWBQWVk3n2Xiyh6UrKwsTZ48ecS/X1RUxAXuIM63szjfzuJ8O4vz7ayxON/D9Zz0Y5IsAAAwDgEFAAAYJ6MCSn5+vjZv3qz8/Px0NyUjcL6dxfl2FufbWZxvZ5lwvl05SRYAAHhbRvWgAAAAdyCgAAAA4xBQAACAcQgoAADAOBkTULZv366KigoVFBRoxowZ+vnPf57uJnnC4cOHVV1drWAwKJ/Pp7179ya8blmWXnrpJQWDQY0bN05z587Vhx9+mJ7GekBNTY3uueceFRYWatKkSXrwwQf18ccfJxzDObfPjh07dNddd8WLVc2aNUv/+Z//GX+dcz22ampq5PP5tG7duvhznHP7vPTSS/L5fAmPQCAQfz3d5zojAsq//uu/at26dXrxxRf1/vvv64//+I+1dOlS/fKXv0x301zv6tWrmjZtmrZt2zbo69/73vf06quvatu2bTp58qQCgYAWLlwY308JqTl06JCefvppHT9+XA0NDfrNb36jRYsW6erVq/FjOOf2mTx5sl555RWdOnVKp06d0v33368VK1bEb9Kc67Fz8uRJ/eM//qPuuuuuhOc55/b6yle+olAoFH+cPn06/lraz7WVAWbOnGn91V/9VcJzX/rSl6wXXnghTS3yJknWnj174j/HYjErEAhYr7zySvy57u5uy+/3W6+//noaWug97e3tliTr0KFDlmVxzp0wYcIE65/+6Z8412Oos7PTuv32262Ghgbrvvvus5555hnLsri+7bZ582Zr2rRpg75mwrn2fA/K9evX1djYqEWLFiU8v2jRIh09ejRNrcoMra2tCofDCec+Pz9f9913H+feJpFIRJJUXFwsiXM+lqLRqOrq6nT16lXNmjWLcz2Gnn76aT3wwANasGBBwvOcc/t9+umnCgaDqqio0KOPPqpf/OIXksw4167cLDAV//d//6doNKrS0tKE50tLSxUOh9PUqszQf34HO/fnzp1LR5M8xbIsPffcc5ozZ46qqqokcc7HwunTpzVr1ix1d3fr937v97Rnzx5VVlbGb9Kca3vV1dWpqalJJ0+eHPAa17e97r33Xv3kJz/RHXfcof/93//Vd7/7Xc2ePVsffvihEefa8wGln8/nS/jZsqwBz2FscO7Hxpo1a/TBBx/oyJEjA17jnNvnzjvvVHNzs371q1/p3/7t37Ry5UodOnQo/jrn2j5tbW165plntH//fhUUFAx5HOfcHkuXLo3/76lTp2rWrFm67bbb9OMf/1hf+9rXJKX3XHt+iGfixInKzs4e0FvS3t4+IBnCXv2zwTn39lu7dq3eeecdvffee5o8eXL8ec65/fLy8vRHf/RH+upXv6qamhpNmzZNP/jBDzjXY6CxsVHt7e2aMWOGcnJylJOTo0OHDumHP/yhcnJy4ueVcz42xo8fr6lTp+rTTz814vr2fEDJy8vTjBkz1NDQkPB8Q0ODZs+enaZWZYaKigoFAoGEc3/9+nUdOnSIcz9ClmVpzZo1euutt3TgwAFVVFQkvM45H3uWZamnp4dzPQbmz5+v06dPq7m5Of746le/qj/7sz9Tc3Oz/vAP/5BzPoZ6enr00UcfqayszIzr25GpuGlWV1dn5ebmWm+++aZ15swZa926ddb48eOt//mf/0l301yvs7PTev/9963333/fkmS9+uqr1vvvv2+dO3fOsizLeuWVVyy/32+99dZb1unTp63HHnvMKisrszo6OtLccndavXq15ff7rYMHD1qhUCj++PWvfx0/hnNun02bNlmHDx+2WltbrQ8++MD69re/bWVlZVn79++3LItz7YQbV/FYFufcTuvXr7cOHjxo/eIXv7COHz9uLVu2zCosLIx/N6b7XGdEQLEsy/r7v/9769Zbb7Xy8vKs6dOnx5dlYnTee+89S9KAx8qVKy3L6luqtnnzZisQCFj5+fnW17/+dev06dPpbbSLDXauJVk/+tGP4sdwzu3zl3/5l/H7xi233GLNnz8/Hk4si3PthM8HFM65fR555BGrrKzMys3NtYLBoPXQQw9ZH374Yfz1dJ9rn2VZljN9NQAAAMnx/BwUAADgPgQUAABgHAIKAAAwDgEFAAAYh4ACAACMQ0ABAADGIaAAAADjEFAAAIBxCCgAAMA4BBQAAGAcAgoAADAOAQUAABjn/wHpVCIgQAEx8AAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "## 构造点的数据结构\n",
    "\n",
    "import math\n",
    "from sys import maxsize\n",
    "class Point:\n",
    "    def __init__(self, x, y):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.is_left = False\n",
    "    def __str__(self):\n",
    "        return \"({0},{1})\".format(self.x, self.y)\n",
    "    def distance(self, other_point):\n",
    "        if other_point == self:\n",
    "            return maxsize\n",
    "        return math.sqrt((self.x - other_point.x)**2 +(self.y - other_point.y)**2)\n",
    "    \n",
    "point_list = []\n",
    "for x, y in zip(x_t, y_t):\n",
    "    p = Point(x, y)\n",
    "    point_list.append(p)\n",
    "\n",
    "point_list.sort(key=lambda p: p.y)\n",
    "# for p in point_list:\n",
    "    # 调用__str__方法\n",
    "    # print(p)    \n",
    "\n",
    "point_list_x = [point.x for point in point_list]\n",
    "point_list_y = [point.y for point in point_list]\n",
    "number = [num for num in range(1,len(point_list)+1)]\n",
    "\n",
    "plt.scatter(number,point_list_x)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "fca79709",
   "metadata": {},
   "outputs": [],
   "source": [
    "def seperate_points_by_median(points, median):\n",
    "    L = []\n",
    "    R = []\n",
    "    i = 0\n",
    "    left = []\n",
    "    right = []\n",
    "    for p in points:\n",
    "        if p.x <= median:\n",
    "            left.append(p)\n",
    "            p.is_left = True\n",
    "        else:\n",
    "            right.append(p)\n",
    "    \n",
    "    left_more = len(left) - int(len(points) / 2)\n",
    "    right_more = len(right) - int(len(right) / 2)\n",
    "\n",
    "    if left_more > 0:\n",
    "        for p in left:\n",
    "            if p.x >= median:\n",
    "                p.is_left = False\n",
    "                left_more -= 1\n",
    "            if left_more == 0:\n",
    "                break\n",
    "\n",
    "    if right_more > 0:\n",
    "        for p in right:\n",
    "            if p.x <= median:\n",
    "                p.is_left = True\n",
    "                right_more -= 1\n",
    "    \n",
    "    for p in points:\n",
    "        if p.is_left :\n",
    "            L.append(p)\n",
    "        else:\n",
    "            R.append(p)\n",
    "\n",
    "    return L, R\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "6c8f38db",
   "metadata": {},
   "outputs": [],
   "source": [
    "def arrange_array_by_pivot(array, pivot):\n",
    "    \"\"\" 将数组分为3部分， 第1部分元素小于pivot, 第二部分元素等于pivot，第三部分元素大于pivot \"\"\"\n",
    "    i = 0\n",
    "    j = len(array) - 1\n",
    "\n",
    "    while i < j:\n",
    "        if array[i] < pivot:\n",
    "            i += 1\n",
    "        elif array[i] >= pivot:\n",
    "            temp = array[j]\n",
    "            array[j] = array[i]\n",
    "            array[i] = temp\n",
    "            j -= 1\n",
    "        \n",
    "    if array[i] < pivot:\n",
    "        i += 1\n",
    "    \n",
    "    k = i\n",
    "    S1 = array[0:i]\n",
    "    j = len(array) - 1\n",
    "\n",
    "    while i < j:\n",
    "        if array[i] == pivot:\n",
    "            i += 1\n",
    "        else:\n",
    "            temp = array[j]\n",
    "            array[j] = array[i]\n",
    "            array[i] = temp\n",
    "            j -= 1\n",
    "        \n",
    "    if array[i] == pivot:\n",
    "        i += 1\n",
    "    \n",
    "    S2 = array[k:i]\n",
    "    S3 = array[i:]\n",
    "\n",
    "    return S1, S2, S3\n",
    "    \n",
    "\n",
    "def selection(array, k):\n",
    "    \"\"\" 查找数组中第k小的元素 \"\"\"\n",
    "    if len(array) <= 1:\n",
    "        return array[0]\n",
    "    if k > len(array):\n",
    "        raise Exception('Out of range!')\n",
    "    \n",
    "    pivot = array[0]\n",
    "    is_good_pivot = False\n",
    "\n",
    "    while is_good_pivot != True:\n",
    "        pivot = random.choice(array)\n",
    "\n",
    "        S1, S2, S3 = arrange_array_by_pivot(array, pivot)\n",
    "        if len(S1) <= int((3/4)*len(array)) and len(S3) <= int((3/4)*len(array)):\n",
    "            is_good_pivot = True\n",
    "    \n",
    "    if len(S1) > 0 and k <= len(S1):\n",
    "        return selection(S1, k)\n",
    "    elif len(S2) > 0 and k <= len(S1) + len(S2):\n",
    "        return pivot\n",
    "    else:\n",
    "        return selection(S3, k - len(S1) - len(S2))\n",
    "    raise Exception('error')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1be124b3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "median is : 153\n",
      "Points in L are ['(149,150)', '(112,164)', '(145,169)', '(122,173)', '(104,179)', '(107,183)', '(101,188)', '(140,192)', '(108,194)', '(101,199)', '(125,201)', '(139,203)', '(124,221)', '(132,223)', '(111,224)', '(133,232)', '(110,237)', '(100,251)', '(123,256)', '(135,261)', '(196,270)', '(115,271)', '(107,280)', '(136,292)', '(104,297)', '(135,298)']: \n",
      "Points in R are ['(196,153)', '(180,153)', '(160,164)', '(169,172)', '(195,184)', '(188,195)', '(192,202)', '(196,202)', '(183,213)', '(189,215)', '(183,216)', '(189,218)', '(153,221)', '(177,232)', '(175,260)', '(154,261)', '(180,265)', '(186,265)', '(182,275)', '(162,277)', '(181,283)', '(195,293)', '(177,294)', '(189,295)']: \n",
      "median is : 123\n",
      "Points in L are ['(149,150)', '(112,164)', '(145,169)', '(122,173)', '(104,179)', '(107,183)', '(101,188)', '(140,192)', '(108,194)', '(101,199)', '(125,201)', '(139,203)', '(124,221)', '(132,223)', '(111,224)', '(133,232)', '(110,237)', '(100,251)', '(135,261)', '(196,270)', '(115,271)', '(107,280)', '(136,292)', '(104,297)', '(135,298)']: \n",
      "Points in R are ['(123,256)']: \n",
      "median is : 122\n",
      "Points in L are ['(149,150)', '(112,164)', '(145,169)', '(104,179)', '(107,183)', '(101,188)', '(140,192)', '(108,194)', '(101,199)', '(125,201)', '(139,203)', '(124,221)', '(132,223)', '(111,224)', '(133,232)', '(110,237)', '(100,251)', '(135,261)', '(196,270)', '(115,271)', '(107,280)', '(136,292)', '(104,297)', '(135,298)']: \n",
      "Points in R are ['(122,173)']: \n",
      "median is : 124\n",
      "Points in L are ['(149,150)', '(112,164)', '(145,169)', '(104,179)', '(107,183)', '(101,188)', '(140,192)', '(108,194)', '(101,199)', '(125,201)', '(139,203)', '(132,223)', '(111,224)', '(133,232)', '(110,237)', '(100,251)', '(135,261)', '(196,270)', '(115,271)', '(107,280)', '(136,292)', '(104,297)', '(135,298)']: \n",
      "Points in R are ['(124,221)']: \n",
      "median is : 115\n",
      "Points in L are ['(149,150)', '(112,164)', '(145,169)', '(104,179)', '(107,183)', '(101,188)', '(140,192)', '(108,194)', '(101,199)', '(125,201)', '(139,203)', '(132,223)', '(111,224)', '(133,232)', '(110,237)', '(100,251)', '(135,261)', '(196,270)', '(107,280)', '(136,292)', '(104,297)', '(135,298)']: \n",
      "Points in R are ['(115,271)']: \n",
      "median is : 125\n",
      "Points in L are ['(149,150)', '(112,164)', '(145,169)', '(104,179)', '(107,183)', '(101,188)', '(140,192)', '(108,194)', '(101,199)', '(139,203)', '(132,223)', '(111,224)', '(133,232)', '(110,237)', '(100,251)', '(135,261)', '(196,270)', '(107,280)', '(136,292)', '(104,297)', '(135,298)']: \n",
      "Points in R are ['(125,201)']: \n",
      "median is : 112\n",
      "Points in L are ['(149,150)', '(145,169)', '(104,179)', '(107,183)', '(101,188)', '(140,192)', '(108,194)', '(101,199)', '(139,203)', '(132,223)', '(111,224)', '(133,232)', '(110,237)', '(100,251)', '(135,261)', '(196,270)', '(107,280)', '(136,292)', '(104,297)', '(135,298)']: \n",
      "Points in R are ['(112,164)']: \n",
      "median is : 132\n",
      "Points in L are ['(149,150)', '(145,169)', '(104,179)', '(107,183)', '(101,188)', '(140,192)', '(108,194)', '(101,199)', '(139,203)', '(111,224)', '(133,232)', '(110,237)', '(100,251)', '(135,261)', '(196,270)', '(107,280)', '(136,292)', '(104,297)', '(135,298)']: \n",
      "Points in R are ['(132,223)']: \n",
      "median is : 111\n",
      "Points in L are ['(149,150)', '(145,169)', '(104,179)', '(107,183)', '(101,188)', '(140,192)', '(108,194)', '(101,199)', '(139,203)', '(133,232)', '(110,237)', '(100,251)', '(135,261)', '(196,270)', '(107,280)', '(136,292)', '(104,297)', '(135,298)']: \n",
      "Points in R are ['(111,224)']: \n",
      "median is : 133\n",
      "Points in L are ['(149,150)', '(145,169)', '(104,179)', '(107,183)', '(101,188)', '(140,192)', '(108,194)', '(101,199)', '(139,203)', '(110,237)', '(100,251)', '(135,261)', '(196,270)', '(107,280)', '(136,292)', '(104,297)', '(135,298)']: \n",
      "Points in R are ['(133,232)']: \n",
      "median is : 110\n",
      "Points in L are ['(149,150)', '(145,169)', '(104,179)', '(107,183)', '(101,188)', '(140,192)', '(108,194)', '(101,199)', '(139,203)', '(100,251)', '(135,261)', '(196,270)', '(107,280)', '(136,292)', '(104,297)', '(135,298)']: \n",
      "Points in R are ['(110,237)']: \n",
      "median is : 135\n",
      "Points in L are ['(149,150)', '(145,169)', '(104,179)', '(107,183)', '(101,188)', '(140,192)', '(108,194)', '(101,199)', '(139,203)', '(100,251)', '(196,270)', '(107,280)', '(136,292)', '(104,297)']: \n",
      "Points in R are ['(135,261)', '(135,298)']: \n",
      "median is : 108\n",
      "Points in L are ['(149,150)', '(145,169)', '(104,179)', '(107,183)', '(101,188)', '(140,192)', '(101,199)', '(139,203)', '(100,251)', '(196,270)', '(107,280)', '(136,292)', '(104,297)']: \n",
      "Points in R are ['(108,194)']: \n",
      "median is : 107\n",
      "Points in L are ['(149,150)', '(145,169)', '(104,179)', '(101,188)', '(140,192)', '(101,199)', '(139,203)', '(100,251)', '(196,270)', '(107,280)', '(136,292)', '(104,297)']: \n",
      "Points in R are ['(107,183)']: \n",
      "median is : 136\n",
      "Points in L are ['(149,150)', '(145,169)', '(104,179)', '(101,188)', '(140,192)', '(101,199)', '(139,203)', '(100,251)', '(196,270)', '(107,280)', '(104,297)']: \n",
      "Points in R are ['(136,292)']: \n",
      "median is : 107\n",
      "Points in L are ['(149,150)', '(145,169)', '(104,179)', '(101,188)', '(140,192)', '(101,199)', '(139,203)', '(100,251)', '(196,270)', '(104,297)']: \n",
      "Points in R are ['(107,280)']: \n",
      "median is : 139\n",
      "Points in L are ['(149,150)', '(145,169)', '(104,179)', '(101,188)', '(140,192)', '(101,199)', '(100,251)', '(196,270)', '(104,297)']: \n",
      "Points in R are ['(139,203)']: \n",
      "median is : 104\n",
      "Points in L are ['(149,150)', '(145,169)', '(101,188)', '(140,192)', '(101,199)', '(100,251)', '(196,270)', '(104,297)']: \n",
      "Points in R are ['(104,179)']: \n",
      "median is : 140\n",
      "Points in L are ['(149,150)', '(145,169)', '(101,188)', '(101,199)', '(100,251)', '(196,270)', '(104,297)']: \n",
      "Points in R are ['(140,192)']: \n",
      "median is : 104\n",
      "Points in L are ['(149,150)', '(145,169)', '(101,188)', '(101,199)', '(100,251)', '(196,270)']: \n",
      "Points in R are ['(104,297)']: \n",
      "median is : 145\n",
      "Points in L are ['(149,150)', '(101,188)', '(101,199)', '(100,251)', '(196,270)']: \n",
      "Points in R are ['(145,169)']: \n",
      "median is : 101\n",
      "Points in L are ['(149,150)', '(101,199)', '(100,251)', '(196,270)']: \n",
      "Points in R are ['(101,188)']: \n",
      "median is : 149\n",
      "Points in L are ['(101,199)', '(100,251)', '(196,270)']: \n",
      "Points in R are ['(149,150)']: \n",
      "median is : 101\n",
      "Points in L are ['(100,251)', '(196,270)']: \n",
      "Points in R are ['(101,199)']: \n",
      "closest pair of L is (100,251), (196,270), with distance 97.86214794290998\n",
      "closest pair of R is (101,199), (101,199), with distance 9223372036854775807\n",
      "Points in rectangle : ['(101,199)', '(100,251)', '(196,270)']\n",
      "current point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "found close pair between L and R with point(101,199), (100,251) and distance 52.009614495783374\n",
      "follow point:  (196,270)\n",
      "current point:  (100,251)\n",
      "follow point:  (196,270)\n",
      "current point:  (196,270)\n",
      "closest pair of L is (101,199), (100,251), with distance 52.009614495783374\n",
      "closest pair of R is (149,150), (149,150), with distance 9223372036854775807\n",
      "Points in rectangle : ['(149,150)', '(101,199)', '(100,251)', '(196,270)']\n",
      "current point:  (149,150)\n",
      "follow point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "follow point:  (196,270)\n",
      "current point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "follow point:  (196,270)\n",
      "current point:  (100,251)\n",
      "follow point:  (196,270)\n",
      "current point:  (196,270)\n",
      "closest pair of L is (101,199), (100,251), with distance 52.009614495783374\n",
      "closest pair of R is (101,188), (101,188), with distance 9223372036854775807\n",
      "Points in rectangle : ['(149,150)', '(101,188)', '(101,199)', '(100,251)']\n",
      "current point:  (149,150)\n",
      "follow point:  (101,188)\n",
      "follow point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "current point:  (101,188)\n",
      "follow point:  (101,199)\n",
      "found close pair between L and R with point(101,188), (101,199) and distance 11.0\n",
      "follow point:  (100,251)\n",
      "current point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "current point:  (100,251)\n",
      "closest pair of L is (101,188), (101,199), with distance 11.0\n",
      "closest pair of R is (145,169), (145,169), with distance 9223372036854775807\n",
      "Points in rectangle : ['(149,150)', '(145,169)']\n",
      "current point:  (149,150)\n",
      "follow point:  (145,169)\n",
      "current point:  (145,169)\n",
      "closest pair of L is (101,188), (101,199), with distance 11.0\n",
      "closest pair of R is (104,297), (104,297), with distance 9223372036854775807\n",
      "Points in rectangle : ['(101,188)', '(101,199)', '(100,251)', '(104,297)']\n",
      "current point:  (101,188)\n",
      "follow point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "follow point:  (104,297)\n",
      "current point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "follow point:  (104,297)\n",
      "current point:  (100,251)\n",
      "follow point:  (104,297)\n",
      "current point:  (104,297)\n",
      "closest pair of L is (101,188), (101,199), with distance 11.0\n",
      "closest pair of R is (140,192), (140,192), with distance 9223372036854775807\n",
      "Points in rectangle : ['(149,150)', '(145,169)', '(140,192)']\n",
      "current point:  (149,150)\n",
      "follow point:  (145,169)\n",
      "follow point:  (140,192)\n",
      "current point:  (145,169)\n",
      "follow point:  (140,192)\n",
      "current point:  (140,192)\n",
      "closest pair of L is (101,188), (101,199), with distance 11.0\n",
      "closest pair of R is (104,179), (104,179), with distance 9223372036854775807\n",
      "Points in rectangle : ['(104,179)', '(101,188)', '(101,199)', '(100,251)', '(104,297)']\n",
      "current point:  (104,179)\n",
      "follow point:  (101,188)\n",
      "found close pair between L and R with point(104,179), (101,188) and distance 9.486832980505138\n",
      "follow point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "follow point:  (104,297)\n",
      "current point:  (101,188)\n",
      "follow point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "follow point:  (104,297)\n",
      "current point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "follow point:  (104,297)\n",
      "current point:  (100,251)\n",
      "follow point:  (104,297)\n",
      "current point:  (104,297)\n",
      "closest pair of L is (104,179), (101,188), with distance 9.486832980505138\n",
      "closest pair of R is (139,203), (139,203), with distance 9223372036854775807\n",
      "Points in rectangle : ['(145,169)', '(140,192)', '(139,203)']\n",
      "current point:  (145,169)\n",
      "follow point:  (140,192)\n",
      "follow point:  (139,203)\n",
      "current point:  (140,192)\n",
      "follow point:  (139,203)\n",
      "current point:  (139,203)\n",
      "closest pair of L is (104,179), (101,188), with distance 9.486832980505138\n",
      "closest pair of R is (107,280), (107,280), with distance 9223372036854775807\n",
      "Points in rectangle : ['(104,179)', '(101,188)', '(101,199)', '(100,251)', '(107,280)', '(104,297)']\n",
      "current point:  (104,179)\n",
      "follow point:  (101,188)\n",
      "follow point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "follow point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (101,188)\n",
      "follow point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "follow point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "follow point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (100,251)\n",
      "follow point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (104,297)\n",
      "closest pair of L is (104,179), (101,188), with distance 9.486832980505138\n",
      "closest pair of R is (136,292), (136,292), with distance 9223372036854775807\n",
      "Points in rectangle : ['(145,169)', '(140,192)', '(139,203)', '(136,292)']\n",
      "current point:  (145,169)\n",
      "follow point:  (140,192)\n",
      "follow point:  (139,203)\n",
      "follow point:  (136,292)\n",
      "current point:  (140,192)\n",
      "follow point:  (139,203)\n",
      "follow point:  (136,292)\n",
      "current point:  (139,203)\n",
      "follow point:  (136,292)\n",
      "current point:  (136,292)\n",
      "closest pair of L is (104,179), (101,188), with distance 9.486832980505138\n",
      "closest pair of R is (107,183), (107,183), with distance 9223372036854775807\n",
      "Points in rectangle : ['(104,179)', '(107,183)', '(101,188)', '(101,199)', '(100,251)', '(107,280)', '(104,297)']\n",
      "current point:  (104,179)\n",
      "follow point:  (107,183)\n",
      "found close pair between L and R with point(104,179), (107,183) and distance 5.0\n",
      "follow point:  (101,188)\n",
      "follow point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "follow point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (107,183)\n",
      "follow point:  (101,188)\n",
      "follow point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "follow point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (101,188)\n",
      "follow point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "follow point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (101,199)\n",
      "follow point:  (100,251)\n",
      "follow point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (100,251)\n",
      "follow point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (104,297)\n",
      "closest pair of L is (104,179), (107,183), with distance 5.0\n",
      "closest pair of R is (108,194), (108,194), with distance 9223372036854775807\n",
      "Points in rectangle : ['(104,179)', '(107,183)', '(108,194)', '(107,280)', '(104,297)']\n",
      "current point:  (104,179)\n",
      "follow point:  (107,183)\n",
      "follow point:  (108,194)\n",
      "follow point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (107,183)\n",
      "follow point:  (108,194)\n",
      "follow point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (108,194)\n",
      "follow point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (107,280)\n",
      "follow point:  (104,297)\n",
      "current point:  (104,297)\n",
      "closest pair of L is (104,179), (107,183), with distance 5.0\n",
      "closest pair of R is (135,261), (135,298), with distance 37.0\n",
      "Points in rectangle : ['(140,192)', '(139,203)', '(135,261)', '(136,292)', '(135,298)']\n",
      "current point:  (140,192)\n",
      "follow point:  (139,203)\n",
      "follow point:  (135,261)\n",
      "follow point:  (136,292)\n",
      "follow point:  (135,298)\n",
      "current point:  (139,203)\n",
      "follow point:  (135,261)\n",
      "follow point:  (136,292)\n",
      "follow point:  (135,298)\n",
      "current point:  (135,261)\n",
      "follow point:  (136,292)\n",
      "follow point:  (135,298)\n",
      "current point:  (136,292)\n",
      "follow point:  (135,298)\n",
      "current point:  (135,298)\n",
      "closest pair of L is (104,179), (107,183), with distance 5.0\n",
      "closest pair of R is (110,237), (110,237), with distance 9223372036854775807\n",
      "Points in rectangle : ['(107,183)', '(108,194)', '(110,237)', '(107,280)']\n",
      "current point:  (107,183)\n",
      "follow point:  (108,194)\n",
      "follow point:  (110,237)\n",
      "follow point:  (107,280)\n",
      "current point:  (108,194)\n",
      "follow point:  (110,237)\n",
      "follow point:  (107,280)\n",
      "current point:  (110,237)\n",
      "follow point:  (107,280)\n",
      "current point:  (107,280)\n",
      "closest pair of L is (104,179), (107,183), with distance 5.0\n",
      "closest pair of R is (133,232), (133,232), with distance 9223372036854775807\n",
      "Points in rectangle : ['(133,232)', '(135,261)', '(136,292)', '(135,298)']\n",
      "current point:  (133,232)\n",
      "follow point:  (135,261)\n",
      "follow point:  (136,292)\n",
      "follow point:  (135,298)\n",
      "current point:  (135,261)\n",
      "follow point:  (136,292)\n",
      "follow point:  (135,298)\n",
      "current point:  (136,292)\n",
      "follow point:  (135,298)\n",
      "current point:  (135,298)\n",
      "closest pair of L is (104,179), (107,183), with distance 5.0\n",
      "closest pair of R is (111,224), (111,224), with distance 9223372036854775807\n",
      "Points in rectangle : ['(107,183)', '(108,194)', '(111,224)', '(110,237)', '(107,280)']\n",
      "current point:  (107,183)\n",
      "follow point:  (108,194)\n",
      "follow point:  (111,224)\n",
      "follow point:  (110,237)\n",
      "follow point:  (107,280)\n",
      "current point:  (108,194)\n",
      "follow point:  (111,224)\n",
      "follow point:  (110,237)\n",
      "follow point:  (107,280)\n",
      "current point:  (111,224)\n",
      "follow point:  (110,237)\n",
      "follow point:  (107,280)\n",
      "current point:  (110,237)\n",
      "follow point:  (107,280)\n",
      "current point:  (107,280)\n",
      "closest pair of L is (104,179), (107,183), with distance 5.0\n",
      "closest pair of R is (132,223), (132,223), with distance 9223372036854775807\n",
      "Points in rectangle : ['(132,223)', '(133,232)', '(135,261)', '(136,292)', '(135,298)']\n",
      "current point:  (132,223)\n",
      "follow point:  (133,232)\n",
      "follow point:  (135,261)\n",
      "follow point:  (136,292)\n",
      "follow point:  (135,298)\n",
      "current point:  (133,232)\n",
      "follow point:  (135,261)\n",
      "follow point:  (136,292)\n",
      "follow point:  (135,298)\n",
      "current point:  (135,261)\n",
      "follow point:  (136,292)\n",
      "follow point:  (135,298)\n",
      "current point:  (136,292)\n",
      "follow point:  (135,298)\n",
      "current point:  (135,298)\n",
      "closest pair of L is (104,179), (107,183), with distance 5.0\n",
      "closest pair of R is (112,164), (112,164), with distance 9223372036854775807\n",
      "Points in rectangle : ['(112,164)', '(107,183)', '(108,194)', '(111,224)', '(110,237)', '(107,280)']\n",
      "current point:  (112,164)\n",
      "follow point:  (107,183)\n",
      "follow point:  (108,194)\n",
      "follow point:  (111,224)\n",
      "follow point:  (110,237)\n",
      "follow point:  (107,280)\n",
      "current point:  (107,183)\n",
      "follow point:  (108,194)\n",
      "follow point:  (111,224)\n",
      "follow point:  (110,237)\n",
      "follow point:  (107,280)\n",
      "current point:  (108,194)\n",
      "follow point:  (111,224)\n",
      "follow point:  (110,237)\n",
      "follow point:  (107,280)\n",
      "current point:  (111,224)\n",
      "follow point:  (110,237)\n",
      "follow point:  (107,280)\n",
      "current point:  (110,237)\n",
      "follow point:  (107,280)\n",
      "current point:  (107,280)\n",
      "closest pair of L is (104,179), (107,183), with distance 5.0\n",
      "closest pair of R is (125,201), (125,201), with distance 9223372036854775807\n",
      "Points in rectangle : ['(125,201)']\n",
      "current point:  (125,201)\n",
      "closest pair of L is (104,179), (107,183), with distance 5.0\n",
      "closest pair of R is (115,271), (115,271), with distance 9223372036854775807\n",
      "Points in rectangle : ['(112,164)', '(111,224)', '(110,237)', '(115,271)']\n",
      "current point:  (112,164)\n",
      "follow point:  (111,224)\n",
      "follow point:  (110,237)\n",
      "follow point:  (115,271)\n",
      "current point:  (111,224)\n",
      "follow point:  (110,237)\n",
      "follow point:  (115,271)\n",
      "current point:  (110,237)\n",
      "follow point:  (115,271)\n",
      "current point:  (115,271)\n",
      "closest pair of L is (104,179), (107,183), with distance 5.0\n",
      "closest pair of R is (124,221), (124,221), with distance 9223372036854775807\n",
      "Points in rectangle : ['(125,201)', '(124,221)']\n",
      "current point:  (125,201)\n",
      "follow point:  (124,221)\n",
      "current point:  (124,221)\n",
      "closest pair of L is (104,179), (107,183), with distance 5.0\n",
      "closest pair of R is (122,173), (122,173), with distance 9223372036854775807\n",
      "Points in rectangle : ['(122,173)', '(125,201)', '(124,221)']\n",
      "current point:  (122,173)\n",
      "follow point:  (125,201)\n",
      "follow point:  (124,221)\n",
      "current point:  (125,201)\n",
      "follow point:  (124,221)\n",
      "current point:  (124,221)\n",
      "closest pair of L is (104,179), (107,183), with distance 5.0\n",
      "closest pair of R is (123,256), (123,256), with distance 9223372036854775807\n",
      "Points in rectangle : ['(122,173)', '(125,201)', '(124,221)', '(123,256)']\n",
      "current point:  (122,173)\n",
      "follow point:  (125,201)\n",
      "follow point:  (124,221)\n",
      "follow point:  (123,256)\n",
      "current point:  (125,201)\n",
      "follow point:  (124,221)\n",
      "follow point:  (123,256)\n",
      "current point:  (124,221)\n",
      "follow point:  (123,256)\n",
      "current point:  (123,256)\n",
      "median is : 183\n",
      "Points in L are ['(180,153)', '(160,164)', '(169,172)', '(153,221)', '(177,232)', '(175,260)', '(154,261)', '(180,265)', '(182,275)', '(162,277)', '(181,283)', '(177,294)']: \n",
      "Points in R are ['(196,153)', '(195,184)', '(188,195)', '(192,202)', '(196,202)', '(183,213)', '(189,215)', '(183,216)', '(189,218)', '(186,265)', '(195,293)', '(189,295)']: \n",
      "median is : 177\n",
      "Points in L are ['(180,153)', '(160,164)', '(169,172)', '(153,221)', '(175,260)', '(154,261)', '(180,265)', '(182,275)', '(162,277)', '(181,283)']: \n",
      "Points in R are ['(177,232)', '(177,294)']: \n",
      "median is : 175\n",
      "Points in L are ['(180,153)', '(160,164)', '(169,172)', '(153,221)', '(154,261)', '(180,265)', '(182,275)', '(162,277)', '(181,283)']: \n",
      "Points in R are ['(175,260)']: \n",
      "median is : 169\n",
      "Points in L are ['(180,153)', '(160,164)', '(153,221)', '(154,261)', '(180,265)', '(182,275)', '(162,277)', '(181,283)']: \n",
      "Points in R are ['(169,172)']: \n",
      "median is : 180\n",
      "Points in L are ['(160,164)', '(153,221)', '(154,261)', '(182,275)', '(162,277)', '(181,283)']: \n",
      "Points in R are ['(180,153)', '(180,265)']: \n",
      "median is : 162\n",
      "Points in L are ['(160,164)', '(153,221)', '(154,261)', '(182,275)', '(181,283)']: \n",
      "Points in R are ['(162,277)']: \n",
      "median is : 160\n",
      "Points in L are ['(153,221)', '(154,261)', '(182,275)', '(181,283)']: \n",
      "Points in R are ['(160,164)']: \n",
      "median is : 181\n",
      "Points in L are ['(153,221)', '(154,261)', '(182,275)']: \n",
      "Points in R are ['(181,283)']: \n",
      "median is : 154\n",
      "Points in L are ['(153,221)', '(182,275)']: \n",
      "Points in R are ['(154,261)']: \n",
      "closest pair of L is (153,221), (182,275), with distance 61.29437168288782\n",
      "closest pair of R is (154,261), (154,261), with distance 9223372036854775807\n",
      "Points in rectangle : ['(153,221)', '(154,261)', '(182,275)']\n",
      "current point:  (153,221)\n",
      "follow point:  (154,261)\n",
      "found close pair between L and R with point(153,221), (154,261) and distance 40.01249804748511\n",
      "follow point:  (182,275)\n",
      "current point:  (154,261)\n",
      "follow point:  (182,275)\n",
      "found close pair between L and R with point(154,261), (182,275) and distance 31.304951684997057\n",
      "current point:  (182,275)\n",
      "closest pair of L is (154,261), (182,275), with distance 31.304951684997057\n",
      "closest pair of R is (181,283), (181,283), with distance 9223372036854775807\n",
      "Points in rectangle : ['(153,221)', '(154,261)', '(182,275)', '(181,283)']\n",
      "current point:  (153,221)\n",
      "follow point:  (154,261)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (154,261)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "found close pair between L and R with point(182,275), (181,283) and distance 8.06225774829855\n",
      "current point:  (181,283)\n",
      "closest pair of L is (182,275), (181,283), with distance 8.06225774829855\n",
      "closest pair of R is (160,164), (160,164), with distance 9223372036854775807\n",
      "Points in rectangle : ['(160,164)', '(153,221)', '(154,261)']\n",
      "current point:  (160,164)\n",
      "follow point:  (153,221)\n",
      "follow point:  (154,261)\n",
      "current point:  (153,221)\n",
      "follow point:  (154,261)\n",
      "current point:  (154,261)\n",
      "closest pair of L is (182,275), (181,283), with distance 8.06225774829855\n",
      "closest pair of R is (162,277), (162,277), with distance 9223372036854775807\n",
      "Points in rectangle : ['(160,164)', '(154,261)', '(162,277)']\n",
      "current point:  (160,164)\n",
      "follow point:  (154,261)\n",
      "follow point:  (162,277)\n",
      "current point:  (154,261)\n",
      "follow point:  (162,277)\n",
      "current point:  (162,277)\n",
      "closest pair of L is (182,275), (181,283), with distance 8.06225774829855\n",
      "closest pair of R is (180,153), (180,265), with distance 112.0\n",
      "Points in rectangle : ['(180,153)', '(180,265)', '(182,275)', '(181,283)']\n",
      "current point:  (180,153)\n",
      "follow point:  (180,265)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (180,265)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (181,283)\n",
      "closest pair of L is (182,275), (181,283), with distance 8.06225774829855\n",
      "closest pair of R is (169,172), (169,172), with distance 9223372036854775807\n",
      "Points in rectangle : ['(169,172)', '(162,277)']\n",
      "current point:  (169,172)\n",
      "follow point:  (162,277)\n",
      "current point:  (162,277)\n",
      "closest pair of L is (182,275), (181,283), with distance 8.06225774829855\n",
      "closest pair of R is (175,260), (175,260), with distance 9223372036854775807\n",
      "Points in rectangle : ['(180,153)', '(169,172)', '(175,260)', '(180,265)', '(182,275)', '(181,283)']\n",
      "current point:  (180,153)\n",
      "follow point:  (169,172)\n",
      "follow point:  (175,260)\n",
      "follow point:  (180,265)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (169,172)\n",
      "follow point:  (175,260)\n",
      "follow point:  (180,265)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (175,260)\n",
      "follow point:  (180,265)\n",
      "found close pair between L and R with point(175,260), (180,265) and distance 7.0710678118654755\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (180,265)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (181,283)\n",
      "closest pair of L is (175,260), (180,265), with distance 7.0710678118654755\n",
      "closest pair of R is (177,232), (177,294), with distance 62.0\n",
      "Points in rectangle : ['(180,153)', '(177,232)', '(175,260)', '(180,265)', '(182,275)', '(181,283)', '(177,294)']\n",
      "current point:  (180,153)\n",
      "follow point:  (177,232)\n",
      "follow point:  (175,260)\n",
      "follow point:  (180,265)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "follow point:  (177,294)\n",
      "current point:  (177,232)\n",
      "follow point:  (175,260)\n",
      "follow point:  (180,265)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "follow point:  (177,294)\n",
      "current point:  (175,260)\n",
      "follow point:  (180,265)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "follow point:  (177,294)\n",
      "current point:  (180,265)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "follow point:  (177,294)\n",
      "current point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "follow point:  (177,294)\n",
      "current point:  (181,283)\n",
      "follow point:  (177,294)\n",
      "current point:  (177,294)\n",
      "median is : 189\n",
      "Points in L are ['(188,195)', '(183,213)', '(183,216)', '(189,218)', '(186,265)', '(189,295)']: \n",
      "Points in R are ['(196,153)', '(195,184)', '(192,202)', '(196,202)', '(189,215)', '(195,293)']: \n",
      "median is : 188\n",
      "Points in L are ['(183,213)', '(183,216)', '(189,218)', '(186,265)', '(189,295)']: \n",
      "Points in R are ['(188,195)']: \n",
      "median is : 186\n",
      "Points in L are ['(183,213)', '(183,216)', '(189,218)', '(189,295)']: \n",
      "Points in R are ['(186,265)']: \n",
      "median is : 189\n",
      "Points in L are ['(183,213)', '(183,216)']: \n",
      "Points in R are ['(189,218)', '(189,295)']: \n",
      "closest pair of L is (183,213), (183,216), with distance 3.0\n",
      "closest pair of R is (189,218), (189,295), with distance 77.0\n",
      "Points in rectangle : ['(189,218)', '(189,295)']\n",
      "current point:  (189,218)\n",
      "follow point:  (189,295)\n",
      "current point:  (189,295)\n",
      "closest pair of L is (183,213), (183,216), with distance 3.0\n",
      "closest pair of R is (186,265), (186,265), with distance 9223372036854775807\n",
      "Points in rectangle : ['(183,213)', '(183,216)', '(189,218)', '(186,265)', '(189,295)']\n",
      "current point:  (183,213)\n",
      "follow point:  (183,216)\n",
      "follow point:  (189,218)\n",
      "follow point:  (186,265)\n",
      "follow point:  (189,295)\n",
      "current point:  (183,216)\n",
      "follow point:  (189,218)\n",
      "follow point:  (186,265)\n",
      "follow point:  (189,295)\n",
      "current point:  (189,218)\n",
      "follow point:  (186,265)\n",
      "follow point:  (189,295)\n",
      "current point:  (186,265)\n",
      "follow point:  (189,295)\n",
      "current point:  (189,295)\n",
      "closest pair of L is (183,213), (183,216), with distance 3.0\n",
      "closest pair of R is (188,195), (188,195), with distance 9223372036854775807\n",
      "Points in rectangle : ['(188,195)', '(189,218)', '(186,265)', '(189,295)']\n",
      "current point:  (188,195)\n",
      "follow point:  (189,218)\n",
      "follow point:  (186,265)\n",
      "follow point:  (189,295)\n",
      "current point:  (189,218)\n",
      "follow point:  (186,265)\n",
      "follow point:  (189,295)\n",
      "current point:  (186,265)\n",
      "follow point:  (189,295)\n",
      "current point:  (189,295)\n",
      "median is : 195\n",
      "Points in L are ['(192,202)', '(189,215)', '(195,293)']: \n",
      "Points in R are ['(196,153)', '(195,184)', '(196,202)']: \n",
      "median is : 192\n",
      "Points in L are ['(189,215)', '(195,293)']: \n",
      "Points in R are ['(192,202)']: \n",
      "closest pair of L is (189,215), (195,293), with distance 78.23042886243178\n",
      "closest pair of R is (192,202), (192,202), with distance 9223372036854775807\n",
      "Points in rectangle : ['(192,202)', '(189,215)', '(195,293)']\n",
      "current point:  (192,202)\n",
      "follow point:  (189,215)\n",
      "found close pair between L and R with point(192,202), (189,215) and distance 13.341664064126334\n",
      "follow point:  (195,293)\n",
      "current point:  (189,215)\n",
      "follow point:  (195,293)\n",
      "current point:  (195,293)\n",
      "median is : 196\n",
      "Points in L are ['(195,184)']: \n",
      "Points in R are ['(196,153)', '(196,202)']: \n",
      "closest pair of L is (195,184), (195,184), with distance 9223372036854775807\n",
      "closest pair of R is (196,153), (196,202), with distance 49.0\n",
      "Points in rectangle : ['(196,153)', '(195,184)', '(196,202)']\n",
      "current point:  (196,153)\n",
      "follow point:  (195,184)\n",
      "found close pair between L and R with point(196,153), (195,184) and distance 31.016124838541646\n",
      "follow point:  (196,202)\n",
      "current point:  (195,184)\n",
      "follow point:  (196,202)\n",
      "found close pair between L and R with point(195,184), (196,202) and distance 18.027756377319946\n",
      "current point:  (196,202)\n",
      "closest pair of L is (192,202), (189,215), with distance 13.341664064126334\n",
      "closest pair of R is (195,184), (196,202), with distance 18.027756377319946\n",
      "Points in rectangle : ['(196,153)', '(195,184)', '(192,202)', '(196,202)', '(189,215)', '(195,293)']\n",
      "current point:  (196,153)\n",
      "follow point:  (195,184)\n",
      "follow point:  (192,202)\n",
      "follow point:  (196,202)\n",
      "follow point:  (189,215)\n",
      "follow point:  (195,293)\n",
      "current point:  (195,184)\n",
      "follow point:  (192,202)\n",
      "follow point:  (196,202)\n",
      "follow point:  (189,215)\n",
      "follow point:  (195,293)\n",
      "current point:  (192,202)\n",
      "follow point:  (196,202)\n",
      "found close pair between L and R with point(192,202), (196,202) and distance 4.0\n",
      "follow point:  (189,215)\n",
      "follow point:  (195,293)\n",
      "current point:  (196,202)\n",
      "follow point:  (189,215)\n",
      "follow point:  (195,293)\n",
      "current point:  (189,215)\n",
      "follow point:  (195,293)\n",
      "current point:  (195,293)\n",
      "closest pair of L is (183,213), (183,216), with distance 3.0\n",
      "closest pair of R is (192,202), (196,202), with distance 4.0\n",
      "Points in rectangle : ['(188,195)', '(192,202)', '(189,215)', '(189,218)', '(186,265)', '(189,295)']\n",
      "current point:  (188,195)\n",
      "follow point:  (192,202)\n",
      "follow point:  (189,215)\n",
      "follow point:  (189,218)\n",
      "follow point:  (186,265)\n",
      "follow point:  (189,295)\n",
      "current point:  (192,202)\n",
      "follow point:  (189,215)\n",
      "follow point:  (189,218)\n",
      "follow point:  (186,265)\n",
      "follow point:  (189,295)\n",
      "current point:  (189,215)\n",
      "follow point:  (189,218)\n",
      "follow point:  (186,265)\n",
      "follow point:  (189,295)\n",
      "current point:  (189,218)\n",
      "follow point:  (186,265)\n",
      "follow point:  (189,295)\n",
      "current point:  (186,265)\n",
      "follow point:  (189,295)\n",
      "current point:  (189,295)\n",
      "closest pair of L is (175,260), (180,265), with distance 7.0710678118654755\n",
      "closest pair of R is (183,213), (183,216), with distance 3.0\n",
      "Points in rectangle : ['(180,153)', '(183,213)', '(183,216)', '(180,265)', '(186,265)', '(182,275)', '(181,283)']\n",
      "current point:  (180,153)\n",
      "follow point:  (183,213)\n",
      "follow point:  (183,216)\n",
      "follow point:  (180,265)\n",
      "follow point:  (186,265)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (183,213)\n",
      "follow point:  (183,216)\n",
      "follow point:  (180,265)\n",
      "follow point:  (186,265)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (183,216)\n",
      "follow point:  (180,265)\n",
      "follow point:  (186,265)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (180,265)\n",
      "follow point:  (186,265)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (186,265)\n",
      "follow point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (182,275)\n",
      "follow point:  (181,283)\n",
      "current point:  (181,283)\n",
      "closest pair of L is (104,179), (107,183), with distance 5.0\n",
      "closest pair of R is (183,213), (183,216), with distance 3.0\n",
      "Points in rectangle : ['(153,221)', '(154,261)']\n",
      "current point:  (153,221)\n",
      "follow point:  (154,261)\n",
      "current point:  (154,261)\n",
      "divide and conque -> p1: (183,213), p2: (183,216), distance: 3.0\n"
     ]
    }
   ],
   "source": [
    "def find_closest_pair(points):\n",
    "    if len(points) == 1:\n",
    "        return maxsize, points[0], points[0]\n",
    "    if len(points) == 2:\n",
    "        return points[0].distance(points[1]), points[0], points[1]\n",
    "    \n",
    "    points_x = [p.x for p in points]\n",
    "    x_median = selection(points_x, int(len(points_x) / 2) + 1)\n",
    "    print(\"median is :\", x_median)    # 调试信息\n",
    "    L, R = seperate_points_by_median(points, x_median)\n",
    "    L_str = [str(pl) for pl in L]\n",
    "    R_str = [str(pr) for pr in R]\n",
    "    print(\"Points in L are {0}: \".format(L_str))\n",
    "    print(\"Points in R are {0}: \".format(R_str))\n",
    "\n",
    "    L_d, point1_L, point2_L = find_closest_pair(L)\n",
    "    R_d, point1_R, point2_R = find_closest_pair(R)\n",
    "\n",
    "    print(\"closest pair of L is {0}, {1}, with distance {2}\".format(point1_L, point2_L, L_d))\n",
    "    print(\"closest pair of R is {0}, {1}, with distance {2}\".format(point1_R, point2_R, R_d))\n",
    "    point_1 = None\n",
    "    point_2 = None\n",
    "\n",
    "    d = min(L_d, R_d)\n",
    "    if L_d == d:\n",
    "        point_1 = point1_L\n",
    "        point_2 = point2_L\n",
    "    else:\n",
    "        point_1 = point1_R\n",
    "        point_2 = point2_R\n",
    "\n",
    "    points_in_rectangle = []\n",
    "    for p in points:\n",
    "        if p.x >= x_median - d and p.x <= x_median + d:\n",
    "            points_in_rectangle.append(p)\n",
    "    p_rectangel_str = [str(prs) for prs in points_in_rectangle]\n",
    "    print(\"Points in rectangle :\", p_rectangel_str)\n",
    "\n",
    "    for k in range(0, len(points_in_rectangle)):\n",
    "        follows = min(len(points_in_rectangle) -k - 1, 7)\n",
    "        p = points_in_rectangle[k]\n",
    "        print(\"current point: \", p)\n",
    "        for j in range(k + 1, k + 1 + follows):\n",
    "            print(\"follow point: \", points_in_rectangle[j])\n",
    "            pd = p.distance(points_in_rectangle[j])\n",
    "            if pd < d:\n",
    "                d = pd\n",
    "                point_1 = p\n",
    "                point_2 = points_in_rectangle[j]\n",
    "                print('found close pair between L and R with point{0}, {1} and distance {2}'.format(point_1, point_2, d))\n",
    "                \n",
    "    return d, point_1, point_2\n",
    "\n",
    "d, p1, p2 = find_closest_pair(point_list)\n",
    "\n",
    "print('divide and conque -> p1: {0}, p2: {1}, distance: {2}'.format(p1, p2, d))\n",
    "\n",
    "         \n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env_py38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
